Extended Euclid

[nntp.online.no]

I just discovered (?) an ultra simple modular
inverse function, which works for unsigned (large) numbers.
Comments?

int Inverse(int x, int y)
{
return x!=1?(1+(x-1)*Inverse(y%x,x)%x*y)/x:1;
}

[Larry Hammick]

nntp.online.no <x...@x.com> wrote in message
news:k7ab9.11452$0p1.1...@news2.ulv.nextra.no...

It looks nice, but the C source is somewhat garbled on my Windows machine,
and not everyone speaks C. Can you spell out the (reentrant) routine in
pseudocode?
Larry

[Phil Carmody]

I think it can be transformed into easier-to-read code:

Firstly, replace
(x-1)*Inverse(y%x,x)%x*y
by
(x-Inverse(y%x,x))%x*y
which gets rid of the (x-1) which confuses the code a bit.
Fortunatley it also gets rid of a multiply.

For an inverse to be defined in Inverse(x,y), x must not be 0, as will its inverse
and therefore we can assume that Inverse(a,x) returns a number in [1..x), and
therefore (x-Inverse(y%x,x)) is in [1..x) too, and therefore the %x is elidable.

For readability I'd reverse teh sense of the ?: too.

int Inverse(int x, int y)
{

return x==1?1:(1+(x-Inverse(y%x,x))*y)/x;
}

Which reduces the op count quite a bit (5 to 3), and is more readable.

Whether it works is another matter, I'm writing this on the fly, just from
cursory inspection!

Phil

[Bill Dubuque]

nntp.online.no" <x...@x.com> wrote:
>
> I just discovered (?) an ultra simple modular inverse function,

> which works for unsigned (large) [coprime] numbers. Comments?
>
> int I(int x, int y)
> {
> return x!=1 ? (1+(x-1)*y*(I(y%x,x)%x)/x : 1;
> }
>
> i.e. 1/x mod y = (1 - y (1/y mod x))/x

This is well-known, being a special case of the CRT
(Chinese Remainder Theorem), viz. r=xz, a=1, b=0 in:

CRT: r = a (mod y) => r = a + (b-a) y (1/y mod x)
r = b (mod x)

-> xz = 1 (mod y) => xz = 1 + (0-1) y (1/y mod x)
xz = 0 (mod x)
=> z = 1/x (1 - y (1/y mod x))
-Bill Dubuque