combinat-0.2.7.2: Generate and manipulate various combinatorial objects.

Safe Haskell Safe Haskell2010

Math.Combinat.Numbers.Primes

Description

Prime numbers and related number theoretical stuff.

Synopsis

# List of prime numbers

primes :: [Integer] Source

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.

# Prime factorization

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

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

The naive trial division algorithm.

# Integer logarithm

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

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

# Integer square root

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.

Smallest integer whose square is larger or equal to the input

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)```

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

# Modulo `m` arithmetic

Efficient powers modulo m.

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

# Prime testing

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