Euclidean Modular Inverse AlgorithmDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/