{- Copyright (C) 2011 Dr. Alistair Ward This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. -} {- | [@AUTHOR@] Dr. Alistair Ward [@DESCRIPTION@] * Exports a common interface for primality-implementations. * Provides utilities for these implementations. -} module Factory.Math.Primality( -- * Type-classes Algorithmic(..), -- * Functions carmichaelNumbers, -- ** Predicates areCoprime, isFermatWitness, isCarmichaelNumber ) where import qualified Control.DeepSeq import qualified Factory.Math.Power as Math.Power -- | Defines the methods expected of a primality-testing algorithm. class Algorithmic algorithm where isPrime :: (Control.DeepSeq.NFData i, Integral i, Show i) => algorithm -> 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>. -} areCoprime :: Integral i => i -> i -> Bool areCoprime i = (== 1) . gcd i {- | * 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. -} isFermatWitness :: (Integral i, Show i) => i -> Bool isFermatWitness i = not . all isFermatPseudoPrime $ filter (areCoprime i) [2 .. pred i] where isFermatPseudoPrime base = Math.Power.raiseModulo base (pred i) i == 1 -- CAVEAT: a /Fermat Pseudo-prime/ must also be a /composite/ number. {- | * 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>. -} isCarmichaelNumber :: ( Algorithmic algorithm, Control.DeepSeq.NFData i, Integral i, Show i ) => algorithm -> i -> Bool isCarmichaelNumber algorithm i = not $ or [ i <= 2, even i, isFermatWitness i, isPrime algorithm i ] -- | An ordered list of the /Carmichael/ numbers; <http://en.wikipedia.org/wiki/Carmichael_number>. carmichaelNumbers :: ( Algorithmic algorithm, Control.DeepSeq.NFData i, Integral i, Show i ) => algorithm -> [i] carmichaelNumbers algorithm = isCarmichaelNumber algorithm `filter` [3, 5 ..]