Solving Modular FormulaDate: 11/04/2008 at 03:45:10 From: Rajareddy Subject: Modular formula If a = b^e mod c, then b = ?. Here a, e, c, are known. Date: 11/04/2008 at 23:15:17 From: Doctor Vogler Subject: Re: Modular formula Hi Rajareddy, Thanks for writing to Dr. Math. The answer, of course, is a^(1/e) (mod c), but in some sense this just dodges your question. You probably want to know how to compute a^(1/e) (mod c). First you have to factor c. When c is not a prime or prime power, then it's usually easiest to solve the problem mod the factors of c and then reassemble the answer using the Chinese Remainder Theorem. When a and c have a factor in common, and c is a prime or prime power, then the answer is usually easy. For example, if c is prime, and c divides a, then b = 0 mod c as well. If c = p^k for some prime p, then b = 0 mod p^m where m is the smallest integer greater than or equal to k/e. Now suppose that a and c do not have a factor in common. Then you compute phi(c), the Euler phi function (a.k.a. totient function). Now, the easy case is when e and phi(c) are relatively prime to one another. Then you just need to compute the multiplicative inverse of e mod phi(c), which you can do, for example, by the Extended Euclidean Algorithm (among other ways). Then raise a to this multiplicative inverse mod c, and that is your answer. When e and phi(c) are not relatively prime, then there is *not* a unique solution. There are either no solutions or gcd(e, phi(c)) solutions. Determining whether there are any solutions is not hard. Let g = gcd(e, phi(c)). If there is at least one solution, then a^(phi(c)/g) = (b^phi(c))^(e/g) = 1^(e/g) = 1 (mod c). It turns out (when c is a prime or power of a prime) that a^(phi(c)/g) will be 1 mod c *only* if there is a solution, so that's how you check. When there is a solution, and g is not 1, then it takes more work to find a root. When g = 2, you can use any of several methods for modular square roots, such as the Tonelli-Shanks Algorithm. When g is larger, the best algorithm that I know of would be a search that runs in O(sqrt(c)) time. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/