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

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.

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search