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

### Euclidean Modular Inverse Algorithm

```
Date: 08/26/97 at 23:33:01
From: Graham K. Coleman
Subject: Euclidean Modular Inverse Algorithm

I'm trying to figure out a simple way how to program an algorithm
for finding the modular inverse... the number that when multiplied
by the original number produces bar 1.

The algorithm starts out with the Euclidean algorithm for finding
the Greatest Common factor.... which, because we are using (assume)
that the pair of numbers we use is relatively prime, always returns a
one...

a mod b (b being larger)

b = a * q1 + r1 (remainder)
a = r1 * q2 + r2
r1 = r2 * q3 + r3

and so on until remainder = 1

real number example

63 mod 200

200 = 63 * 3 + 11
63 = 11 * 5 + 8
11 = 8 * 1 + 3
8 = 3 * 2 + 2
3 = 2 * 1 + 1

then once you get a 1 as remainder, you back substitute the
equations and simplify according to the remainders...

1 = 3 - (2)
1 = 3 - (8 -2(3))
1 = 3 - 8 + 2(3)
1 = -8 + 3(3)
1 = -8 + 3(11 - (8))
1 = -8 + 3(11) -3(8)
1 = 3(11) -4(8)
1 = 3(11) -4(63 - 5(11))
1 = 3(11) -4(63) + 20(11)
1 = -4(63) + 23(11)
1 = -4(63) + 23(200 - 3(63))
1 = -4(63) + 23(200) - 69(63)
1 = -73(63) + 23(200)

The number being multiplied by the original key (smaller number)
is the modular inverse... (-73) which is 127 in mod 200....

127 * 63 = bar 1(mod 200)

------------------------------------------------------------

So, could you give me a psuedocode representation of how the
algorithm is supposed to look with variables... recursive, iterative,
or otherwise....?

Thanks a lot.

Graham Coleman
```

```
Date: 08/27/97 at 15:32:13
From: Doctor Wilkinson
Subject: Re: Euclidean Modular Inverse Algorithm

As you noticed, the problem amounts to finding x and y such that

ax + by = 1

Let's suppose a > b.  Now we can certainly solve

ax + by = a
and
ax + by = b

The first equation has the solution   x0 = 1, y0 = 0
and the second has the solution       x1 = 0, y1 = 1

What we're going to do is run the Euclidean algorithm and keep
updating x0, y0, x1, y1 as we go, so that we always have

ax0 + by0 = r0
and
ax1 + by1 = r1

where r0 and r1 are the current remainders and r0 > r1.
So if we initialize

r0 = a and r1 = b, we are starting off right.

Now divide r0 by r1, so that

r0 = qr1 + r, where r is smaller than r1

Then

r = r0 - q * r1 = ax0 + by0 - q * (ax1 + by1)
= a(x0 - qx1) + b(y0 - qy1)

so letting

x = x0 - q * x1
y = y0 - q * y1

we can turn the crank to the next step by substituting

r0 = r1; r1 = r; x0 = x1; x1 = x; y0 = y1; y1 = y

I'll leave the details like when to quit up to you.

-Doctor Wilkinson,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms

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