Modulus algebra: c = ( m * x ) mod p
Date: 03/14/2003 at 10:50:42 From: firstname.lastname@example.org 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: email@example.com Subject: Thank you (Modulus algebra) Thank you for your help. I can finish the last part of my program now. Thanks a lot!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.