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!