Basic Number Theory

module NumberTheoryFundamentals

NumberTheoryFundamentals.hs
This module provides various functions which are fundamental to almost everything we want to do in number theory.
Exports
d `divides` n
n `splitWith` p - returns (s,t) such that n == p^s * t
power (idG,multG) x n - returns x^n in the semigroup with given identity and multiplication.
extendedEuclid a b - returns (u,v,d) such that u*a+v*b = d, where d == gcd a b.
intSqrt n - returns floor (sqrt n), but computed to full precision and using only integer operations.
legendreSymbol a p - returns 0 if p divides a, 1 if a is a square mod p, -1 if not.
sqrtsmodp a p - return the square roots of a mod p (if there are any).

module Primes

Primes.hs
This module provides functions to test whether a number is prime, and to find prime factorisations. The primality test is probabilistic - this means it's fast - and it has a 1 in 2^50 chance of being wrong. (The received wisdom is that this is less than the chance of a hardware error, so it's okay.) The prime factorisation is not intended to be used with products of large primes. It takes out small factors (< 10000), tests whether what it has left is a prime, and if not, throws an error.
Exports
isPrime :: Integer -> Bool - test whether a number is prime
nextPrime :: Integer -> Integer - find the next prime
primePowerFactors :: Integer -> [(Integer,Int)] - split a number into prime power factors. Not intended for use with products of large primes.
Examples
isPrime (2^127-1) returns True - the 12th Mersenne prime.
nextPrime 1000 returns 1009
primePowerFactors 60 returns [(2,2),(3,1),(5,1)], meaning 2²3¹5¹

module Factoring

Factoring.hs
This module provides functions to factor numbers which are products of two or more large primes. Note however that the bigger the primes, the longer you have to wait.
Exports
primePowerFactorsL :: Integer -> [(Integer,Int)] - a version of primePowerFactors which attempts to factor any unfactored residue.

module FactoringECM

FactoringECM.hs
Factorisation using Lenstra's elliptic curve method.
Exports
findFactorECM n - find a non-trivial factor of n using ECM.

module FactoringCFRAC

FactoringCFRAC.hs
Factorisation using the continued fraction method.
Exports
findFactorCFRAC n - find a non-trivial factor of n using CFRAC.

module ArithmeticFunctions

ArithmeticFunctions.hs
This module contains definitions of several important number-theoretic functions. Most of them are multiplicative functions, which means that if m,n are coprime, then f(mn) = f(m)*f(n).
Exports
eulerTotient n - the Euler totient function, which counts the number of a with 1 <= a < n which are coprime to n.
mobius n - the Mobius function, which is zero if n is divisible by a square, and otherwise -1^k, where k is the number of prime factors of n.
numDivisors n - returns the number of divisors of n - this function is usually called "d" in the literature.
sigma1 n - returns the sum of the divisors of n.
sigma k n - returns the sum of the kth powers of the divisors of n.
Examples
numDivisors 28 returns 6, because the divisors are 1, 2, 4, 7, 14, 28.
sigma1 28 returns 56, which is 1+2+4+7+14+28.
eulerTotient 11 returns 10 - because any prime is coprime to all the numbers less than it