Calculating inverses quickly.

[mgb]

Do you think this would be faster than the extended Euclidean Algorithm for finding inverses?

For a given a find a^-1 (mod m)

1. Let m = r mod a
2. Find r ^-1 mod a
3. Let x = a - r ^-1 (ie, x = -r ^-1 mod a)
4. a^-1 mod m = (xm + 1)/a

If this algorithm is applied recursively, at step 2., it should be possible to reduce the question finding the inverse of a small number and then working back up the chain to find the original inverse.


The reasoning is as follows:-

aa^-1 = km + 1, for some k < a, so km = -1 (mod a)
That is, k = -m ^-1 (mod a)
Adding 1, km + 1 = 0 (mod a)
Whence, (km + 1)/a = a^-1

(Moderator, I meant to post this in the computing forum but posted here by mistake.)

[Dr Sardonicus]

Originally Posted by mgb

Do you think this would be faster than the extended Euclidean Algorithm for finding inverses?

For a given a find a^-1 (mod m)

1. Let m = r mod a
2. Find r ^-1 mod a
3. Let x = a - r ^-1 (ie, x = -r ^-1 mod a)
4. a^-1 mod m = (xm + 1)/a

If this algorithm is applied recursively, at step 2., it should be possible to reduce the question finding the inverse of a small number and then working back up the chain to find the original inverse.
<snip>

If I understand you correctly, you're doing the same sequence of divisions with quotient and remainder as in the Euclidean algorithm.

[mgb]

Originally Posted by Dr Sardonicus

If I understand you correctly, you're doing the same sequence of divisions with quotient and remainder as in the Euclidean algorithm.

Yes but at step 2 the task is reduced to a smaller pair of numbers, to which the extended Euclidean algorithm can be applied. This is an immediate saving in processor time. Step 2 = Find r ^-1 mod a

Example:

Find 17 ^-1 mod 223
-223 ^-1 = 8 mod 17
(8*223 + 1)/17 = 105 = 17 ^-1 mod 223