| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Math.Combinat.Numbers.Primes
Description
Prime numbers and related number theoretical stuff.
Synopsis
- divides :: Integer -> Integer -> Bool
- divisors :: Integer -> [Integer]
- squareFreeDivisors :: Integer -> [(Integer, Sign)]
- squareFreeDivisors_ :: Integer -> [Integer]
- divisorSum :: Integer -> Integer
- divisorSum' :: Int -> Integer -> Integer
- moebiusMu :: (Integral a, Num b) => a -> b
- eulerTotient :: Integer -> Integer
- liouvilleLambda :: (Integral a, Num b) => a -> b
- primes :: [Integer]
- primesSimple :: [Integer]
- primesTMWE :: [Integer]
- factorize :: Integer -> [(Integer, Int)]
- factorizeNaive :: Integer -> [(Integer, Int)]
- productOfFactors :: [(Integer, Int)] -> Integer
- integerFactorsTrialDivision :: Integer -> [Integer]
- groupIntegerFactors :: [Integer] -> [(Integer, Int)]
- powerMod :: Integer -> Integer -> Integer -> Integer
- millerRabinPrimalityTest :: Integer -> Integer -> Bool
- isProbablyPrime :: Integer -> Bool
- isVeryProbablyPrime :: Integer -> Bool
Elementary number theory
squareFreeDivisors :: Integer -> [(Integer, Sign)] Source #
List of square-free divisors together with their Mobius mu value (note: the result is not ordered!)
squareFreeDivisors_ :: Integer -> [Integer] Source #
List of square-free divisors (note: the result is not ordered!)
divisorSum :: Integer -> Integer Source #
Sum ofthe of the divisors
eulerTotient :: Integer -> Integer Source #
Euler's totient function
liouvilleLambda :: (Integral a, Num b) => a -> b Source #
The Liouville lambda function
List of prime numbers
primesSimple :: [Integer] Source #
A relatively simple but still quite fast implementation of list of primes. By Will Ness http://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html
primesTMWE :: [Integer] Source #
List of primes, using tree merge with wheel. Code by Will Ness.
Prime factorization
integerFactorsTrialDivision :: Integer -> [Integer] Source #
The naive trial division algorithm.
groupIntegerFactors :: [Integer] -> [(Integer, Int)] Source #
Groups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)]
Modulo m arithmetic
powerMod :: Integer -> Integer -> Integer -> Integer Source #
Efficient powers modulo m.
powerMod a k m == (a^k) `mod` m
Prime testing
millerRabinPrimalityTest :: Integer -> Integer -> Bool Source #
Miller-Rabin Primality Test (taken from Haskell wiki).
We test the primality of the first argument n by using the second argument a as a candidate witness.
If it returs False, then n is composite. If it returns True, then n is either prime or composite.
A random choice between 2 and (n-2) is a good choice for a.
isProbablyPrime :: Integer -> Bool Source #
For very small numbers, we use trial division, for larger numbers, we apply the
Miller-Rabin primality test log4(n) times, with candidate witnesses derived
deterministically from n using a pseudo-random sequence
(which should be based on a cryptographic hash function, but isn't, yet).
Thus the candidate witnesses should behave essentially like random, but the resulting function is still a deterministic, pure function.
TODO: implement the hash sequence, at the moment we use Random instead...
isVeryProbablyPrime :: Integer -> Bool Source #
A more exhaustive version of isProbablyPrime, this one tests candidate
witnesses both the first log4(n) prime numbers and then log4(n) pseudo-random
numbers