Factory.Math.Primality

AUTHOR

Dr. Alistair Ward

DESCRIPTION

• Exports a common interface for primality-implementations.
• Provides utilities for these implementations.

Type-classes

class Algorithmic algorithm where

Defines the methods expected of a primality-testing algorithm.

Methods

isPrime :: (NFData i, Integral i, Show i) => algorithm -> i -> Bool

Instances

Algorithmic factorisationAlgorithm => Algorithmic (Algorithm factorisationAlgorithm)

Functions

carmichaelNumbers :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> [i]

An ordered list of the Carmichael numbers; http://en.wikipedia.org/wiki/Carmichael_number.

Predicates

areCoprime :: Integral i => i -> i -> Bool

True if the two specified integers are relatively prime, i.e. if they share no common positive factors except one.

• 1 and -1 are the only numbers which are coprime to themself.
• http://en.wikipedia.org/wiki/Coprime.
• http://mathworld.wolfram.com/RelativelyPrime.html.

isFermatWitness :: (Integral i, Show i) => i -> Bool

• Tests Fermat's Little Theorem for all applicable values, as a probabilistic primality-test.
• http://en.wikipedia.org/wiki/Fermat%27s_little_theorem.
• http://en.wikipedia.org/wiki/Fermat_primality_test.
• http://en.wikipedia.org/wiki/Fermat_pseudoprime.
• CAVEAT: this primality-test fails for the Carmichael numbers.
• TODO: confirm that all values must be tested.

isCarmichaelNumber :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> Bool

• A Carmichael number is an odd composite number which satisfies Fermat's little theorem.
• http://en.wikipedia.org/wiki/Carmichael_number.
• http://mathworld.wolfram.com/CarmichaelNumber.html.