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 --
> -----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. >
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 > > -- >