Mod, Inverses, and Number Theory
Date: 11/27/2001 at 21:19:35 From: Matt Ronge Subject: Mod, Inverses and Number Theory Hello, I am working on a computer program to do RSA encryption. Everything is working except one equation I can't solve. I need to find a value for d (I already have values for e, p and q): d = e^-1 mod (p-1)(q-1) If I solve this using the methods I know, I always get 0 or 1. For example: p = 5 q = 7 e = 3 d = 3^-1 mod (5-1)(7-1) d = 1/3 mod 24 d = 1 But that isn't the solution. How do you solve this equation? Also, why are 1, 7, 11... their own inverses? I thought an inverse was putting the number under 1/ . Since I can't solve the above equation I have a feeling I'll be having trouble with this also: C = M^e mod n Any special way to solve this? If I can put values in all of them except C, how do I solve it? An example I found online showed this: Solution to linear congruence 11x = 5 ( mod 29 ) Multiply both sides by the inverse of 11 mod ( 29 ): 8 * 11x = 8 * 5 ( mod 29 ) x = 40 = 11 ( mod 29 ) My question here is how can the inverse of 11 be the number 8? How come 40 = 11 ( mod 29 ), shouldn't that be 1? Thanks, and sorry about all the questions.
Date: 11/27/2001 at 22:31:49 From: Doctor Paul Subject: Re: Mod, Inverses and Number Theory The inverse of 3 mod 24 is a number that when multiplied by 3 gives a result that is congruent to 1 mod 24 - that is, the product will be one more than a multiple of 24. However, no such number exists because 3 is not relatively prime to 24 (i.e., gcd(3,24) = 3 and this is greater than one). When you choose e, you have to make sure that gcd(e,m) = 1 where m = (p-1)*(q-1). Choosing e in this manner guarantees that d = e^(-1) mod m exists and is unique. Here's a better example: p = 47 q = 71 then, n = p*q = 3337 and, (p-1)(q-1) = 3220 I choose e to be 79. So, I want to compute the decipher key, d = 79^(-1) mod 3220 The problem can be restated as follows: Solve for d: 79*d = 1 mod 3220 First use the regular Euclidean Algorithm to find gcd(79,3220). The answer had better be one - otherwise we can't be sure that a solution exists. Proceed as follows: 3220 = 40*79 + 60 79 = 1*60 + 19 60 = 3*19 + 3 19 = 6*3 + 1 3 = 3*1 + 0 The last nonzero remainder is the gcd. Thus gcd(79,3220) = 1 (as expected). Now write this gcd (one) as a linear combination of 19 and 3220 by working back up the tree that we just created: The next to the last line gives: 1 = 19-6*3 = 19-6*(60-3*19) = 19*19 - 6*60 = 19*(79-60) - 6*60 = 19*79 - 25*60 = 19*79 - 25*(3220-40*79) = 1019*79 - 25*3220 Thus 1019*79 - 25*3220 = 1 Now do "mod 3220" on both sides to obtain: 1019*79 = 1 mod 3220 (the term that contains 3220 goes away because 3220 = 0 mod 3220). Thus d = 1019. So the inverse of 79 mod 3220 is 1019. Another way of saying this is that 79*1019 will be one more than a multiple of 3220. This can be generalized quite easily if you're interested in teaching the algorithm to a computer. The Extended Euclidean Algorithm is basically a set of instructions that explain how to generate a number from the previous numbers (using the relations that are obvious from the construction of the tree that we used above to find the gcd). >Since I can't solve the above equation I have a feeling I'll be >having trouble with this also: >C = M^e mod n >Any special way to solve this? If I can put values in all of them >except C how do I solve it. If you know everything except C, just compute M^e and reduce mod n. All you're doing is finding the remainder upon division by n. See below for an explanation of how to compute 40 mod 29. >An example I found online showed this: >Solution to linear congruence 11x = 5 ( mod 29 ) >Multiply both sides by the inverse of 11 mod ( 29 ): >8 * 11x = 8 * 5 ( mod 29 ) >x = 40 = 11 ( mod 29 ) > >My question here is how is the inverse of 11 the number 8? >How come 40 = 11 ( mod 29 ), shouldn't that be 1? 8 is the inverse of 11 mod 29 because 8*29 = 1 mod 29. Another way of saying this is 8*29 is one more than a multiple of 29. You can either see this by inspection or, if you need to compute the inverse of 11 mod 29, proceed as in the first part above. 40 = 11 mod 29 because 40 is 11 more than a multiple of 29. That is, when we divide 40 by 29, we get a remainder of 11: 40 = 1*29 + 11 ^^ the remainder I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.