Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell98 |

`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.

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.

`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 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.