Skip to content

Modular inverses

2 messages · SJ Robson-Davis, William Dunlap

SJ Robson-Davis
# 
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:
Warning message:
probable complete loss of accuracy in modulus
so this method does not work. Any ideas?

Thanks,

Samuel

--
William Dunlap
# 
Brute force works:
   > f<-function(k, p) which(((1:(p-1))*k)%%p == 1)
   > f(10,p=13)
   [1] 4
You can precompute the mapping from k to 1/k mod p
if you will be working with the same p a lot.  Use
sapply() or mapply() if you will be working on a vector
of k and p.

Bill Dunlap
Spotfire, TIBCO Software
wdunlap tibco.com