Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/