rabin: Miller-Rabin Test

In numbers: Number-Theoretic Functions

Miller-Rabin Test

Description

Probabilistic Miller-Rabin primality test.

Usage

  miller_rabin(n)

Arguments

n	natural number.

Details

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.

Value

Returns TRUE or FALSE.

Note

miller_rabin() will only work if package gmp has been loaded by the user separately.

References

https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

See Also

isPrime

Examples

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)

numbers documentation built on Nov. 23, 2022, 9:06 a.m.