View Source Prime.Fermat (prime v0.1.1)
Implementation of Fermat-test.
This module provides the primality test based on Fermat's Little Theorem.
The methodology is essentially probablistic, which means even if the result says the number given is a prime, there is no strong guarantee that it actually is. It only tells the chance is good it is. In practice, the more times you give it a try, the more probable the number is a prime.
Also, there is a series of contrary evidences with which Fermat test is known to fail. The sequence is known as Carmichael numbers, and they are infinite.
Despite the deficiency, Fermat test is largely entrusted,
widely employed algorithm for larger primes, partly because
Carmichael numbers are not very abundant (there are 255 of
them below 10^8
) and they get even rarer as number gets
bigger. Abelson and Sussman in SICP
put it that the risk of gaining false positive is
"less than the chance that cosmic radiation will cause
the computer to cause an error".
With all of that said, Prime.MillerRabin
implements
another famous algorithm which overcomes the pitfall.
This module is only expected to be utilized for learning
purpose, otherwise go look at Prime.MillerRabin
.
Link to this section Summary
Link to this section Functions
Specs
test(pos_integer()) :: boolean()
Returns the result of fermat-test.
Examples
iex> Prime.Fermat.test(1)
false
iex> Prime.Fermat.test(2)
true
iex> Prime.Fermat.test(3)
true
iex> Prime.Fermat.test(42)
false
iex> Prime.Fermat.test(561)
true # false positive: the first carmichael number.