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:

   WWW Interactive Mathematics Server (WIMS)
   http://wims.unice.fr/wims/ 

(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) 
as the final answer.

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)

 201545*(78261)^16 = 218961 (already computed)
 (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)

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/