Miller-Rabin Test
Probabilistic Miller-Rabin primality test.
miller_rabin(n)
n |
natural number. |
The Miller-Rabin test is an efficient probabilistic primality test based
on strong pseudoprimes. This implementation uses the first seven prime
numbers (if necessary) as test cases. It is thus exact for all numbers
n < 341550071728321.
Returns TRUE or FALSE.
miller_rabin() will only work if package gmp has been loaded
by the user separately.
miller_rabin(2)
## Not run:
miller_rabin(4294967297) #=> FALSE
miller_rabin(4294967311) #=> TRUE
# Rabin-Miller 10 times faster than nextPrime()
N <- n <- 2^32 + 1
system.time(while (!miller_rabin(n)) n <- n + 1) # 0.003
system.time(p <- nextPrime(N)) # 0.029
N <- c(2047, 1373653, 25326001, 3215031751, 2152302898747,
3474749660383, 341550071728321)
for (n in N) {
p <- nextPrime(n)
T <- system.time(r <- miller_rabin(p))
cat(n, p, r, T[3], "\n")}
## End(Not run)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.