Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Modulus algebra: c = ( m * x ) mod p

Date: 03/14/2003 at 10:50:42
From: fatfoolhk@yahoo.com.hk
Subject: Modulus algebra

Can anybody tell me an efficient algorithm or solving method to solve 
the following problem written in Java?

c = ( m * x ) mod p

if c, x and p is known, what is the value of m if 

1.) 0 <= m < p
2.) p is a prime no

I used a for-loop to substitute m with each value between 0 and p to
do the calculation. But if prime number (p) is very large, it takes a
long time.


Date: 03/14/2003 at 14:47:43
From: Doctor Rob
Subject: Re: Modulus algebra

Thanks for writing to Ask Dr. Math.

There are actually two such methods.

First of all, if x = 0 and c = 0, any value of m will work. Next, if x 
= 0 and c is nonzero, no value of m will work. This means that we can 
assume that x is nonzero.

Both methods involve computing a value of z such that x*z = 1 (mod p).  
This z is called the inverse of x. Once this value is known, you can 
multiply your equation on both sides by this z, and you get

   c*z = (m*x)*z = m*(x*z) = m*1 = m (mod p).

The first method depends on something called Fermat's Little Theorem:  
If x is nonzero and p is a prime number, then

   x^(p-1) = 1 (mod p).

That means that

   x*x^(p-2) = x^(p-1) = 1 (mod p),

so

   z = x^(p-2) (mod p).

That reduces the problem to that of efficient computation of 
exponentials modulo p. This can be done using the binary (or base-2) 
expansion of the exponent.

To compute z = x^e (mod p), proceed as follows.

1. Write e = SUM e[i]*2^i, where each e[i] is either 0 or 1,
   and the sum is over 0 <= i <= n.
2. Start with k = n and z = 1.
3. Replace z by z^2 (mod p).
4. If e[k] = 1, replace z by z*x (mod p).
5. If k > 0, replace k by k - 1 and return to step 3 above.
6. Stop.

Then z is the correct value.

The second method involves using the Extended Euclidean
Algorithm, as follows.

1. Start with y = 0, z = 1, a = p, b = x.
2. Divide a by b, getting quotient q and remainder r:
   a = q*b + r, 0 <= r < b.
3. Set t = y - q*z, z = y, y = t, a = b, and b = r.
4. If r > 1, go to step 2 above.
5. If z < 0, replace z by z + p.

Then z is the correct value.

Now recall that m = z*c (mod p) in either case.

Both methods require about log(p) steps. The former uses one or two 
multiplications and modular reductions at each step. The latter uses 
one division, one multiplication, and one subtraction at each step.  
Both are very efficient.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/ 


Date: 03/15/2003 at 09:25:39
From: fatfoolhk@yahoo.com.hk
Subject: Thank you (Modulus algebra)

Thank you for your help. I can finish the last part of my program now. 
Thanks a lot!
Associated Topics:
High School Calculators, Computers
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/