module Factory.Math.Primality(
Algorithmic(..),
carmichaelNumbers,
areCoprime,
isFermatWitness,
isCarmichaelNumber
) where
import qualified Control.DeepSeq
import qualified Factory.Math.Power as Math.Power
class Algorithmic algorithm where
isPrime :: (Control.DeepSeq.NFData i, Integral i, Show i) => algorithm -> i -> Bool
areCoprime :: Integral i => i -> i -> Bool
areCoprime :: i -> i -> Bool
areCoprime i
i = (i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== i
1) (i -> Bool) -> (i -> i) -> i -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> i -> i
forall a. Integral a => a -> a -> a
gcd i
i
isFermatWitness :: (Integral i, Show i) => i -> Bool
isFermatWitness :: i -> Bool
isFermatWitness i
i = Bool -> Bool
not (Bool -> Bool) -> ([i] -> Bool) -> [i] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> Bool) -> [i] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all i -> Bool
isFermatPseudoPrime ([i] -> Bool) -> [i] -> Bool
forall a b. (a -> b) -> a -> b
$ (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
filter (i -> i -> Bool
forall i. Integral i => i -> i -> Bool
areCoprime i
i) [i
2 .. i -> i
forall a. Enum a => a -> a
pred i
i] where
isFermatPseudoPrime :: i -> Bool
isFermatPseudoPrime i
base = i -> i -> i -> i
forall i power.
(Integral i, Integral power, Show power) =>
i -> power -> i -> i
Math.Power.raiseModulo i
base (i -> i
forall a. Enum a => a -> a
pred i
i) i
i i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== i
1
isCarmichaelNumber :: (
Algorithmic algorithm,
Control.DeepSeq.NFData i,
Integral i,
Show i
) => algorithm -> i -> Bool
isCarmichaelNumber :: algorithm -> i -> Bool
isCarmichaelNumber algorithm
algorithm i
i = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
or [
i
i i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i
2,
i -> Bool
forall a. Integral a => a -> Bool
even i
i,
i -> Bool
forall i. (Integral i, Show i) => i -> Bool
isFermatWitness i
i,
algorithm -> i -> Bool
forall algorithm i.
(Algorithmic algorithm, NFData i, Integral i, Show i) =>
algorithm -> i -> Bool
isPrime algorithm
algorithm i
i
]
carmichaelNumbers :: (
Algorithmic algorithm,
Control.DeepSeq.NFData i,
Integral i,
Show i
) => algorithm -> [i]
carmichaelNumbers :: algorithm -> [i]
carmichaelNumbers algorithm
algorithm = algorithm -> i -> Bool
forall algorithm i.
(Algorithmic algorithm, NFData i, Integral i, Show i) =>
algorithm -> i -> Bool
isCarmichaelNumber algorithm
algorithm (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
`filter` [i
3, i
5 ..]