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
_____________________________________________

Solving Modular Formula

Date: 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/ 
Associated Topics:
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/