finite-fields-0.2: Arithmetic in finite fields
Safe HaskellSafe-Inferred



Prime numbers and related number theoretical stuff.


Integer logarithm

integerLog2 :: Integer -> Integer Source #

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

ceilingLog2 :: Integer -> Integer Source #

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

Integer square root

integerSquareRoot :: Integer -> Integer Source #

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 Source #

Smallest integer whose square is larger or equal to the input

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

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) Source #

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

Elementary number theory

divisors :: Integer -> [Integer] Source #

Divisors of n (note: the result is not ordered!)

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

divisorSum' :: Int -> Integer -> Integer Source #

Sum of k-th powers of the divisors

moebiusMu :: (Integral a, Num b) => a -> b Source #

The Moebius mu function (naive implementation)

eulerTotient :: Integer -> Integer Source #

Euler's totient function

liouvilleLambda :: (Integral a, Num b) => a -> b Source #

The Liouville lambda function (naive implementation)

List of prime numbers

primes :: [Integer] Source #

Infinite list of primes, using the TMWE algorithm.

primesSimple :: [Integer] Source #

A relatively simple but still quite fast implementation of list of primes. By Will Ness

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

isPrimeTrialDivision :: Integer -> Bool Source #

Prime testing using trial division

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