| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell98 |
Factory.Math.Primality
Contents
Description
AUTHOR- Dr. Alistair Ward
DESCRIPTION
- Exports a common interface for primality-implementations.
- Provides utilities for these implementations.
- class Algorithmic algorithm where
- carmichaelNumbers :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> [i]
- areCoprime :: Integral i => i -> i -> Bool
- isFermatWitness :: (Integral i, Show i) => i -> Bool
- isCarmichaelNumber :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> i -> Bool
Type-classes
class Algorithmic algorithm where Source
Defines the methods expected of a primality-testing algorithm.
Instances
| Algorithmic factorisationAlgorithm => Algorithmic (Algorithm factorisationAlgorithm) |
Functions
carmichaelNumbers :: (Algorithmic algorithm, NFData i, Integral i, Show i) => algorithm -> [i] Source
An ordered list of the Carmichael numbers; http://en.wikipedia.org/wiki/Carmichael_number.
Predicates
areCoprime :: Integral i => i -> i -> Bool Source
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, Show i) => i -> Bool Source
- 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 Source
- 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.