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/