Associated Topics || Dr. Math Home || Search Dr. Math

### Finding the Exponent with a Modulus

```Date: 05/24/2003 at 11:40:24
From: Sarah
Subject: Finding the exponent with a modulus

I am trying to work out k in the following question :

23^k = 201545 (mod 900001)

I have taken the natural log of both sides

k . ln23 = ln201545 (mod 900001)
k = ln 201545 / ln 23 (mod 900001)

I get the answer as k = 3.895324,
however 23^3 or 23^4 does not = 201545 (mod 900001)
```

```
Date: 05/25/2003 at 10:04:39
From: Doctor Jacques
Subject: Re: Finding the exponent with a modulus

Hi Sarah,

You cannot use logarithms for such arithemtic problems. Logarithms
are defined for real numbers. By analogy, this type of problem is
called the "discrete logarithm" problem, but this is not the same
thing as our usual logarithms.

For solving this problem, all computations have to be carried out in
integers modulo N (in this case, N = 900001).

The first thing to do is to factor N; after that, you can solve the
problem modulo each prime power that divides N, and combine the
results using the Chinese Remainder Theorem. (In this case, 900001 is
prime).

There is no known efficient method for solving this problem, unless
the prime factors of (N-1) are "reasonably small"; in this case, the
prime factors of 900000 are 2, 3, and 5, so we're ok.

For the calculations that follow, you will need special software
(like Mathematica, ...) to perform modular operations. There is also
an online calculator at:

(Select "online calculators," "numeric calculator," use the
"characteristic" field to enter the modulus, and click "register
options.")

Let us look first at a simpler example: we try to solve

11^k = 103 (mod 109)

Note that N = 109 is prime. We start by finding the prime factors of
(N-1):

(N-1) = 108 = 2^2 * 3^3

By Fermat's theorem, we know that x^108 = 1 (mod 109) if x is not a
multiple of 109, so k is defined modulo 108. The idea is to compute
k modulo 2^2 and 3^3.

In the following, unless otherwise stated, all computations are
carried out modulo 109.

Let us start by finding k mod 2. We write k = a_0 + 2n.

We record the powers of h2 = (11^54):

h2^0 = 1
h2^1 = 108

We have:

103^(54) = 11^(54*(a_0 + 2n)) = 11^(54*a_0) * 11^(108*n)
= 11^(54*a_0)
= h2^a_0

(Note that 11^108 = 1 by Fermat's theorem.)

We compute:

103^54 = 108

We can write:

(h2)^a_0 = 108

and we find a_0 = 1, i.e. k = 1 (mod 2)

We now try to find k mod 4. We have k = 1 + 2m + 4n, and we can write:

103^27 = 11^(27*(1 + 2a_1 + 4n))
= 11^(27*(1 + 2a_1)) * 11^(108*n)
= 11^(27*1) * 11^(54a_1)

We compute the modular inverse of 11 (mod 109) by the Euclidean
algorithm, and we find:

11*10 = 1 (mod 109)

which we can write as 11^(-1) = 10.

We now write:

(103*11^(-1))^27 = 11^(54a_1)
49^27 = 11^54a_1 = (h2)^a_1
1 = (h2)^a_1

and we find a_1 = 0. This means that k = 1 + 0*2 = 1 (mod 4).

We must now find k mod 27. We begin by computing the powers of
h3 = 11^(108/3) = 11^36:

h3^0 = 1
h3^1 = 11^36 = 45
h3^2 = 11^(72) = 63

We compute k mod 3. Let us write k = b_0 + 3m. We use the same
technique as before:

103^36 = 11^(36k)
= 11^(36*(b_0 + 3m))
= 11^(36*b_0) * 11^(108*m)
= 11^(36*b_0)
= (h3)^b_0

on the other hand, 103^36 = 63. If we compare that with the powers of
h3 = 11^36, we find that b_0 = 2.

We now compute k mod 9. We write k = 2 + 3b_1 + 9m

103^12 = 11^(12k)
= 11^(12*(2 + 3b_1 + 9m))
= 11^(12*2) * 11^(36b_1) * 11^(108m)
= 11^(12*2) * 11^(36b_1)
= 11^(12*2) * h3^b_1

as we know that the inverse of 11 is 10, this becomes:

(103*10^2)^12 = (h3)^b_1
54^12 = (h3)^b_1
45 = (h3)^b_1

and our table of powers of h3 gives b_1 = 1, so k = 2 + 1*3 = 5
(mod 9)

We compute k mod 27 in the same way, starting with 103^4. In this
case, we have:

(103*10^5)^4 = (11^36)^b_2
45 = (h3)^b_2

and we find b_2 = 1, so k = 2 + 1*3 + 1*9 = 14 (mod 27)

To summarize, we have now:

k = 1 (mod 4)
k = 14 (mod 27)

and, using the Chinese Remainder Theorem, this gives k = 41 (mod 108)

Note that the problem does not always have a solution; for example,
4^k = 2 (mod 5) has no solution. This manifests itself when you look
into the tables of powers for the next exponent and you don't find
the expected value in the list.

In general, to solve g^k = s (mod N), assuming that N is prime, we
factorise N-1, and we compute the modular inverse of g mod N, let
q = g^(-1) (mod N).

Assume that p is a prime factor on N-1, and that the exponent of p in
N-1 is t.

* We compute the powers (0 to p-1) of h_p = g^((N-1)/p).

* We write k = a_0 + a_1*p + ... a_(t-1)*p^(t-1), and we compute the
a_i in order:

* To compute a_0, we compute P = s^((N-1)/p), and we find it in the
table of powers of h_p, i.e. we find a_0 such that h_p^a_0 = P. If
P does not appear in the table, there is no solution.

* To compute a_(i+1), we compute
Q = s*q^(a_0 + a_1*p ... + a_(i)*p^i)), and then
Q^((N-1)/p^(i+2)),
and we look the result in the table of powers of h_p.

Once we have computed k modulo all the prime powers that divide N-1,
we compute k modulo N-1 by the Chinese Remainder Theorem.

As I said before, this algorithm is only practical if all the prime
factors of N-1 are small, since, for each such factor p, we must keep
a table of (p-1) powers of h_p.

For you particular example, this requires A LOT of tedious work, and
I will only give a few results, to allow you to check your
computations (if you have the patience to do them).

We start by checking that 900001 is prime (you can also check that at
the WIMS site above, select "factorize"). We then factorise (N-1):

900000 = 2^5 * 3^2 * 5^5

We compute 23^(-1) = 78261 (this will be used a lot)

We will have to find k mod 2^5, 3^2, and 5^5.

For 2^n, we compute the table of powers of h2 = 23^(900000/2) - they
are 0 and 900000 (=-1).

We write k = a_0 + 2a_1 + 4a_2 + 8a_3 + 16a_4, and we compute the a_i:

(201545)^450000 = 900000, so a_0 = 1

201545*78261 = 595720
(595720)^225000 = 900000, so a_1 = 1, k = 3 (mod 4)

201545*(78261)^3 = 303962
(303962)^112500 = 900000, so a_2 = 1, k = 7 (mod 8)

201545*(78261)^7 = 255827
(255827)^56250 = 900000, so a_3 = 1, k = 15 (mod 16)

201545*(78261)^15 = 536098
(536098)^23125 = 900000, so a_4 = 1, k = 31 (mod 32)

For 3^n, we have the table of powers of h3 = 23^(900000/3):

(h3)^0 = 1
(h3)^1 = 519434
(h3)^2 = 380566

We write k = b_0 + 3b_1, and we compute the b_i:

(201545)^300000 = 380566, so b_0 = 2, k = 2 (mod 3)

201545*(78261)^2 = 691119
(691119)^100000 = 1, so b_1 = 0, k = 2 (mod 9)

For 5^n, we compute the powers of h5 = 23^(900000/5):

(h5)^0 = 1
(h5)^1 = 596402
(h5)^2 = 550388
(h5)^3 = 539252
(h5)^4 = 113959

We write k = c_0 + 5c_1 + 25c_2 + 125c_3 + 625c_4, and we compute the
c_i:

(201545)^180000 = 596402, so c_0 = 1, k = 1 (mod 5)

201545*78261 = 597520
(597520)^36000 = 539252, so c_1 = 3, k = 16 (mod 25)

201545*(78261)^16 = 218961
(218961)^7200 = 1, so c_2 = 0, k = 16 (mod 125)

(218961)^1440 = 113959, so c_3 = 4, k = 516 (mod 625)

201545*(78261)^516 = 753523
(753523)^288 = 596402, so c_4 = 1, k = 1141 (mod 3125)

We have now:

k = 31 (mod 32)
k = 2 (mod 9)
k = 1141 (mod 3125)

and the Chinese remainder theorem gives:

k = 7391 (mod 900000)

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
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