[R] Modular inverses

[Hans W Borchers]

SJ Robson-Davis <sr6827 <at> bristol.ac.uk> writes:

> 
> I want to find the inverse of an integer k mod p (prime.) Is there a
> function that can do this for me? I know i could simply write (k^(p-2)) %%
> p, but i need to do this for large primes (above 100) and this gives the
> warning message:
>     probable complete loss of accuracy in modulus
> so this method does not work. Any ideas?

Computing the inverse mod p applying brute force may not be a very elegant
approach.  With a little knowledge from number theory it is clear that the
(so-called) extended Euclidean algorithms will provide the modular inverse
efficiently, even for very big numbers.

In R the extended Euclidean algorithm is available in the gmp package, see
the 'gcdex' function.  The modular inverse can also directly be calculated
with the 'inv' function, e.g. the invers of 1000001 modulo 1000000001 is:

    library(gmp)
    as.numeric(inv(as.bigz(1000001), as.bigz(1000000001)))
    # [1] 499499501

It's not even necessary that p is prime, only that k and p are relatively
prime.  The integers can be bigger than those handled by double-precision
arithmetics.

Regards
Hans Werner

> Thanks,
> 
> Samuel
> 
> --
>