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

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

some more.

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