# rabin: Miller-Rabin Test In numbers: Number-Theoretic Functions

## Description

Probabilistic Miller-Rabin primality test.

## Usage

 `1` ``` 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

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