gls (11/11/82)
The multiplicative inverse of m(mod p) where p is a prime no. is the least number 'inv_m' such that m * inv_m is congruent to 1(mod p). One simple algorithm is to set inv_m to 1 and test the residue of m * inv_m (mod p) being equal to 1 or not,increment and repeat. The values of inv_m can range from 1 to p. A faster way to do this is instead of incrementing inv_m one can double it every time inside the loop. This approach is defective since one may miss that value of inv_m which is the M.I. of m(mod p). These algorithms will take a long time to compute the M. I. of m(mod p) when m and p are very large(> 200 digits). Is there a faster algorithm to find the M. I.s? Thanks in advance G. L. Srinivasan (..decvax!duke!gls)
leichter (11/13/82)
Multiplicative inverses mod a prime can be found quickly by using the Euclidean Algorithm for GCD. The method goes like this: We have a and p, 0<a<p, p a prime. We wish to find x, 0<x<p, such that ax = 1 (mod p). Write out this last as an equation in integers: We need to find y such that: ax = 1 - yp (y will be negative; I used 1 - yp instead of 1 + yp so the following equations look cleaner.) Turn this around: ax + yp = 1 This is a Diophantine equation, with an infinite number of integer solutions. We wish, essentially, to find the minimal one (in absolute value); the rest differ by multiples of p. The fact that p is prime is not actually relevant, and in a moment we will look at equations of this form in which a non-prime occurs; so let's just look at equations of the form: ax + by = 1 The relation to gcd is: This equation has a root if and only if gcd(a,b) = 1. Now, Euclid's algorithm is based on the fact that gcd(a,b) = gcd(b-a,b). The way to apply it to the above equation is: Suppose, wlog, that b>a. (If a=b, a solution exist iff a=+ or -1.) Consider the equation: ax' + (b-a)y' = 1 If we could solve this equation for x' and y', we'd be done, for we can rewrite it as: a(x'-y') + by' = 1 so x=x'-y', y=y' is our desired solution. But notice that the second equation has strictly smaller constants: a=a and b-a<b. By repeating this reduction, always subtracting the smaller remaining integer from the larger, we get a series of equations that, since we are doing exactly the steps the Euclidean gcd algorithm does, eventually - and quite quickly - gives us an equation of the form ax + y = 1 (or x + by = 1; it's all the same). The minimum root of this one is easy; it's just x=0, y=1! So...back-substitute these values through all the intermediate equations and you are done. Note: There is an obvious speedup, which is needed to get (logarithmic? I forget) performance. If b > a and also (b - a) > a - i.e., b > 2a, we should subtract off two a's in one step. In general, we should subtract floor(b/a) a's. The substitution then results in ax' + (b-f*a)y' = 1 (f = floor(b/a)) and then x = x' - f*a, y = y', and the next time around we will be reducing a. -- Jerry decvax!yale-comix!leichter leichter@yale