Math.Combinat.Numbers.Primes

Prime numbers and related number theoretical stuff.

List of prime numbers

primes :: [Integer]

Infinite list of primes, using the TMWE algorithm.

primesSimple :: [Integer]

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]

List of primes, using tree merge with wheel. Code by Will Ness.

Prime factorization

groupIntegerFactors :: [Integer] -> [(Integer, Int)]

Groups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)]

integerFactorsTrialDivision :: Integer -> [Integer]

The naive trial division algorithm.

Integer logarithm

integerLog2 :: Integer -> Integer

Largest integer k such that 2^k is smaller or equal to n

ceilingLog2 :: Integer -> Integer

Smallest integer k such that 2^k is larger or equal to n

Integer square root

isSquare :: Integer -> Bool

integerSquareRoot :: Integer -> Integer

Integer square root (largest integer whose square is smaller or equal to the input) using Newton's method, with a faster (for large numbers) inital guess based on bit shifts.

ceilingSquareRoot :: Integer -> Integer

Smallest integer whose square is larger or equal to the input

integerSquareRoot' :: Integer -> (Integer, Integer)

We also return the excess residue; that is

 (a,r) = integerSquareRoot' n

means that

 a*a + r = n
 a*a <= n < (a+1)*(a+1)

integerSquareRootNewton' :: Integer -> (Integer, Integer)

Newton's method without an initial guess. For very small numbers (<10^10) it is somewhat faster than the above version.

Modulo m arithmetic

powerMod :: Integer -> Integer -> Integer -> Integer

Efficient powers modulo m.

 powerMod a k m == (a^k) `mod` m

Prime testing

millerRabinPrimalityTest :: Integer -> Integer -> Bool

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.