View Source Prime.MillerRabin (prime v0.1.1)
Implementation of Miller-Rabin-test.
This module provides the primality test based on Miller-Rabin's method.
The methodology is essentially probablistic.
See the doc of Prime.Fermat
for details.
The unignorable difference between fermat-test and miller-rabin-test is that the latter defeats Carmichael numbers while giving up no efficiency. You might feel easier to reason towards employing this algorithm than the fermat-test, although they are equally great formulations of the intrinsic nature of numbers.
Link to this section Summary
Link to this section Functions
Specs
test(pos_integer()) :: boolean()
Returns the result of miller-rabin-test.
Examples
iex> Prime.MillerRabin.test(1)
false
iex> Prime.MillerRabin.test(2)
true
iex> Prime.MillerRabin.test(3)
true
iex> Prime.MillerRabin.test(42)
false
iex> Prime.MillerRabin.test(561)
false # won't get fooled by the first carmichael number.