| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Numeric.Data.ModP.Internal.Primality
Description
Internal tools for modular arithmetic and primality testing. The main
functions are isPrime and findInverse, though others are exported for
testing.
Since: 0.1
Synopsis
- data MaybePrime
- isPrime :: Integer -> MaybePrime
- isPrimeTrials :: Int -> Integer -> MaybePrime
- millerRabin :: Modulus -> Int -> MaybePrime
- isPrimeArithmoi :: Integer -> MaybePrime
- isPrimeDefault :: Integer -> MaybePrime
- newtype Modulus = MkModulus Integer
- newtype Pow = MkPow Integer
- newtype Mult = MkMult Integer
- newtype Rand = MkRand Integer
- trial :: Modulus -> (Pow, Mult) -> Rand -> MaybePrime
- isWitness :: Modulus -> Pow -> Rand -> MaybePrime
- sqProgression :: Modulus -> Integer -> [Integer]
- factor2 :: Modulus -> (Pow, Mult)
- invert :: forall (p :: Nat). KnownNat p => Natural -> Natural
- invertArithmoi :: forall (p :: Nat). KnownNat p => Natural -> Natural
- invertDefault :: forall (p :: Nat). KnownNat p => Natural -> Natural
- data Bezout = MkBezout {}
- newtype R = R' Integer
- newtype S = S' Integer
- newtype T = T' Integer
- findInverse :: Integer -> Modulus -> Integer
- findBezout :: Integer -> Modulus -> Bezout
- errMsg :: String -> String -> String
Primality Testing
data MaybePrime Source #
Result of running Miller-Rabin algorithm. At best we can determine if
some n is definitely composite or "probably prime".
Since: 0.1
Constructors
| Composite | |
| ProbablyPrime |
Instances
isPrime :: Integer -> MaybePrime Source #
Tests primality via the Miller-Rabin algorithm with 100 trials. Returns
Composite if the number is definitely composite, otherwise
ProbablyPrime.
Examples
>>>isPrime 7ProbablyPrime
>>>isPrime 22Composite
>>>isPrime 373ProbablyPrime
Since: 0.1
isPrimeTrials :: Int -> Integer -> MaybePrime Source #
isPrime that takes in an additional Int parameter for the number
of trials to run. The more trials, the more confident we can be in
ProbablyPrime.
Examples
>>>isPrimeTrials 1 91ProbablyPrime
>>>isPrimeTrials 2 91Composite
Note: False positives can be found via:
-- search for "ProbablyPrime" after 1 trial in the composite sequence -- for a given prime p counter p = filter ((== ProbablyPrime) . snd) $ fmap (x -> (x, isPrimeTrials 1 x)) [p + p, p + p + p ..]
Since: 0.1
millerRabin :: Modulus -> Int -> MaybePrime Source #
Miller-Rabin algorithm. Takes in the \(n\) to be tested and the number
of trials to perform. The higher the trials, the higher our confidence
in ProbablyPrime.
Arithmoi vs. Default
By default, our isPrime function implements miller-rabin directly.
Unfortunately, the performance scales poorly (this is an issue with our
implementation, not miller-rabin). Thus we provide the optional flag
arithmoi that instead uses the arithmoi package. Arithmoi is much faster,
though it is not a light dependency, hence the option.
In other words, the flag controls the tradeoff between isPrime speed vs. dependency footprint. So why do we also provide isPrimeDefault and isPrimeArithmoi? Benchmarking. We want to benchmark the difference, hence we need both available when the flag is on.
isPrimeArithmoi :: Integer -> MaybePrime Source #
Uses arithmoi if available, otherwise errors.
isPrimeDefault :: Integer -> MaybePrime Source #
isPrimeTrials with 100 trials.
Helper Types
For the following functions/types, a core concept is rewriting our \(n\) as
\[ n = 2^r d + 1, \]
where \(d\) is odd i.e. we have factored out 2 as much as possible. We use newtypes to track these numbers.
Represents a modulus. When testing for primality, this is the \(n\) in \(n = 2^{r} d + 1\).
Since: 0.1
Instances
| Enum Modulus Source # | |
| Num Modulus Source # | |
| Integral Modulus Source # | |
Defined in Numeric.Data.ModP.Internal.Primality | |
| Real Modulus Source # | |
Defined in Numeric.Data.ModP.Internal.Primality Methods toRational :: Modulus -> Rational # | |
| Show Modulus Source # | |
| Eq Modulus Source # | |
| Ord Modulus Source # | |
Defined in Numeric.Data.ModP.Internal.Primality | |
The \(r\) in \(n = 2^{r} d + 1\).
Since: 0.1
The \(d\) in \(n = 2^{r} d + 1\).
Since: 0.1
Randomly generated \(m \in [2, n - 2] \) for testing \(n\)'s primality.
Since: 0.1
Instances
| Enum Rand Source # | |
Defined in Numeric.Data.ModP.Internal.Primality | |
| Num Rand Source # | |
| Integral Rand Source # | |
| Real Rand Source # | |
Defined in Numeric.Data.ModP.Internal.Primality Methods toRational :: Rand -> Rational # | |
| Show Rand Source # | |
| Eq Rand Source # | |
| Ord Rand Source # | |
| UniformRange Rand Source # | Since: 0.1 |
Defined in Numeric.Data.ModP.Internal.Primality | |
Helper Functions
trial :: Modulus -> (Pow, Mult) -> Rand -> MaybePrime Source #
For \(n, r, d, x\) with \(n = 2^{r} d + 1\) and \(x \in [2, n - 2] \),
returns Composite if \(n\) is definitely composite, ProbablyPrime
otherwise.
Examples
>>>trial 12 (factor2 (12 - 1)) 3Composite
>>>trial 7 (factor2 (7 - 1)) 3ProbablyPrime
Since: 0.1
isWitness :: Modulus -> Pow -> Rand -> MaybePrime Source #
For \(n, r, x\) with \(n = 2^{r} d + 1\) and some
\(x \equiv a^d \pmod n \), returns Composite if \(x\) is a witness to
\(n\) being composite. Otherwise returns ProbablyPrime.
Examples
>>>let (pow, mult) = factor2 (12 - 1)>>>let testVal = 3 ^ mult `mod` 12>>>isWitness 12 pow testValComposite
>>>let (pow, mult) = factor2 (7 - 1)>>>let testVal = 3 ^ mult `mod` 7>>>isWitness 7 pow testValProbablyPrime
Since: 0.1
sqProgression :: Modulus -> Integer -> [Integer] Source #
For \(n, x\), returns the infinite progression
\[ x, x^2, x^4, x^8, \ldots \pmod n. \]
Examples
>>>take 5 $ sqProgression 7 3[3,2,4,2,4]
Since: 0.1
factor2 :: Modulus -> (Pow, Mult) Source #
Given \(n\), returns \((r, d)\) such that \(n = 2^r d\) with \(d\) odd i.e. \(2\) has been factored out.
Examples
>>>factor2 7(MkPow 0,MkMult 7)
>>>factor2 8(MkPow 3,MkMult 1)
>>>factor2 20(MkPow 2,MkMult 5)
Since: 0.1
Multiplicative Inverses
Arithmoi vs. Default
invert :: forall (p :: Nat). KnownNat p => Natural -> Natural Source #
Finds the multiplicative inverse.
invertArithmoi :: forall (p :: Nat). KnownNat p => Natural -> Natural Source #
Finds the multiplicative inverse with arithmoi if available, otherwise errors.
invertDefault :: forall (p :: Nat). KnownNat p => Natural -> Natural Source #
Finds the multiplicative inverse using the built-in algorithm.
Types / Low-level
Since: 0.1
Since: 0.1
Since: 0.1
findInverse :: Integer -> Modulus -> Integer Source #
For \(a, p\), finds the multiplicative inverse of \(a\) in \(\mathbb{Z}/p\mathbb{Z}\). That is, finds e such that
\[ ae \equiv 1 \pmod p. \]
Note: The returned \(e\) is only an inverse when \(a\) and \(p\) are coprime i.e. \((a,p) = 1\). Of course this is guaranteed when \(p\) is prime and \(0 < a < p \), but it otherwise not true in general.
Also, this function requires division, it is partial when the modulus is 0.
Since: 0.1