[R] Modular inverses

[William Dunlap]

> -----Original Message-----
> From: r-help-bounces at r-project.org 
> [mailto:r-help-bounces at r-project.org] On Behalf Of SJ Robson-Davis
> Sent: Friday, November 27, 2009 8:52 AM
> To: r-help at r-project.org
> Subject: [R] Modular inverses
> 
> 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?

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  

> 
> Thanks,
> 
> Samuel
> 
> --
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide 
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>