Infinite list of primes, using the TMWE algorithm.

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

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

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

The naive trial division algorithm.

Efficient powers modulo m.

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

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.

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...

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