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

Functions

Returns the result of fermat-test.

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.