Factory.Math.Primality
Contents
Description
AUTHOR- Dr. Alistair Ward
DESCRIPTION
- Exports a common interface for primality-implementations.
- Provides utilities for these implementations.
- class Algorithm algorithm where
- carmichaelNumbers :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> [i]
- areCoprime :: Integral i => i -> i -> Bool
- isFermatWitness :: Integral i => i -> Bool
- isCarmichaelNumber :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> i -> Bool
Type-classes
Functions
carmichaelNumbers :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> [i]Source
An ordered list of the Carmichael numbers; http://en.wikipedia.org/wiki/Carmichael_number.
Predicates
areCoprime :: Integral i => i -> i -> BoolSource
True if the two specified integers are relatively prime,
i.e. if they share no common positive factors except one.
-
1and-1are the only numbers which are coprime to themself. - http://en.wikipedia.org/wiki/Coprime.
- http://mathworld.wolfram.com/RelativelyPrime.html.
isFermatWitness :: Integral i => i -> BoolSource
- 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 :: (Algorithm algorithm, NFData i, Integral i) => algorithm -> i -> BoolSource
- 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.