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

Functions

Returns the result of miller-rabin-test.

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.