Finding the Exponent with a ModulusDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/