rabin: Miller-Rabin Test

Description Usage Arguments Details Value Note References See Also Examples

Description

Probabilistic Miller-Rabin primality test.

Usage

1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)

Example output

[1] TRUE
[1] FALSE
[1] TRUE
   user  system elapsed 
  0.025   0.000   0.024 
   user  system elapsed 
  0.007   0.000   0.006 
2047 2053 TRUE 0 
1373653 1373677 TRUE 0.001 
25326001 25326023 TRUE 0 
3215031751 3215031767 TRUE 0 
2.152303e+12 2.152303e+12 TRUE 0 
3.47475e+12 3.47475e+12 TRUE 0.001 
3.415501e+14 3.415501e+14 TRUE 0.001 

numbers documentation built on May 15, 2021, 1:08 a.m.