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/