Cunningham project

The Cunningham project aims to find factors of large numbers of the form

$b^n \pm 1$

for b = 2, 3, 5, 6, 7, 10, 11, 12 and large exponents n. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall in 1925. Sometimes it is referred to as one of the oldest continuously ongoing activities in computational number theory.

A recently published version of the tables can be found in "Factorizations of bⁿ ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers" by John Brillhart, Derrick Henry Lehmer, John L. Selfridge, Bryant Tuckerman, & Samuel S. Wagstaff Jr., AMS (2002). The most recent version of the tables can be found at the Cunningham Project website.

The Brent-Montgomery-te Riele table forms an extension to the Cunningham tables, for 12 < b < 1000.

Current limits of the exponents of the Cunningham tables are:

Base	2	3	5	6	7	10	11	12
Limit	1200	600	450	400	400	400	300	300

Properties of Cunningham Factors

In the Cunningham tables, we eliminate two types of factors before factoring the remaining cofactor. The first type is Algebraic Factors, which are derived from a lower exponent. The second type is Aurifeuillian Factors, in which the whole number can be split into two parts directly, for certain combination of values of b and n.

Algebraic Factorizations

It is trivial from elementary algebra that

$(b^{kn}-1) = (b^n-1) \sum _{r=0}^{k-1} b^{rn}$

for any value of k, and

$(b^{kn}+1) = (b^n+1) \sum _{r=0}^{k-1} (-1)^r \cdot b^{rn}$

when k is odd.

Also that, (b²ⁿ − 1) = (bⁿ − 1)(bⁿ + 1).

Thus, it turns out that both b^m − 1 and b^m + 1 are factors of bⁿ − 1, if m divides n and $n \over m$ is even. Only b^m − 1 is a factor of bⁿ − 1, if m divides n and $n \over m$ is odd. Also, b^m + 1 is a factor of bⁿ + 1, if m divides n and $n \over m$ is odd.

Aurifeuillian Factorizations

Main article: Aurifeuillian factorization

Consider the identity

$2^{2h}+1 = L \cdot M\ \mathrm{where} \ L = 2^h-2^k+1,\ M = 2^h+2^k+1,\ h = 2k-1$

This factorization was discovered for one value (n = 14) by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases.

$\begin{align} 3^{3h} + 1 &= (3^h + 1) \cdot L \cdot M\ \mathrm{where}\ L = 3^h - 3^k + 1,\ M = 3^h + 3^k + 1,\ h = 2k - 1 \\ 5^{5h} - 1 &= (5^h - 1) \cdot L \cdot M\ \mathrm{where}\ L = T^2 - T \cdot 5^k + 5^h,\ M = T^2 + T \cdot 5^k + 5^h,\ T = 5^h + 1,\ h = 2k - 1 \\ 6^{6h} + 1 &= (6^{2h} + 1) \cdot L \cdot M\ \mathrm{where}\ L = T^2 - T \cdot 6^k + 6^h,\ M = T^2 + T \cdot 6^k + 6^h,\ T = 6^h + 1,\ h = 2k - 1 \\ 7^{7h} + 1 &= (7^h + 1) \cdot L \cdot M\ \mathrm{where}\ L = T^3 - B,\ M = T^3 + B,\ T = 7^h + 1,\ B = 7^k(T^2 - 7^h),\ h = 2k - 1 \\ 10^{10h} + 1 &= (10^{2h} + 1) \cdot L \cdot M\ \mathrm{where}\ L = A - B,\ M = A + B,\ A = 10^{4h} + 5 \cdot 10^{3h} + 7 \cdot 10^{2h} + 5 \cdot 10^h + 1,\ B = 10^k(10^{3h} + 2 \cdot 10^{2h} + 2 \cdot 10^h + 1),\ h = 2k - 1 \\ 11^{11h} + 1 &= (11^h + 1) \cdot L \cdot M\ \mathrm{where}\ L = A - B,\ M = A + B,\ A = 11^{5h} + 5 \cdot 11^{4h} - 11^{3h} - 11^{2h} + 5 \cdot 11^h + 1,\ B = 11^k(11^{4h} + 11^{3h} - 11^{2h} + 11^h + 1),\ h = 2k - 1 \\ 12^{3h} + 1 &= (12^h + 1) \cdot L \cdot M\ \mathrm{where}\ L = 12^h - 2^h \cdot 3^k + 1,\ M = 12^h + 2^h \cdot 3^k + 1,\ h = 2k - 1 \\ \end{align}$

So, there exist an Aurifeuillian factorization for base b for any exponent of the form b(2k − 1) for integral values of k. Note that the Aurifeuillian factorization of base 5 is on the negative side, while for the other bases 2, 3, 6, 7, 10, 11, 12 it is on the positive side.

Other factors

Once the algebraic and Aurifeuillian factors are removed, the other factors of $b^n \pm 1$ will always be of the form 2kn + 1. When the exponent n is prime, algebraic and Aurifeuillian factors are not possible, except for the trivial factor of b − 1 for bⁿ − 1 and b + 1 for bⁿ + 1.

For Mersenne numbers of the form 2ⁿ − 1, even this trivial factor is not possible for prime values of n, so any factor of it should be of the form 2kn + 1. In general, any factor of $b^n-1 \over b-1$ is of the form 2kn + 1, $b \ge 2$ and n is prime, except when n is a factor of b − 1. In such cases, $b^n-1 \over b-1$ is divisible by n itself.

Cunningham numbers of the form bⁿ − 1 can only be prime if b = 2 and n is prime, assuming that $n \ge 2$, and numbers of the form bⁿ + 1 can only be prime if b is even and n is a power of 2, considering the fact that $n \ge 2$ again. Numbers of the form $(2a)^{2^k}+1$ are known as Generalized Fermat Numbers, which when a = 1, are known as Fermat Numbers. In general, any factor of the Fermat Number $2^{2^k}+1$ is of the form k.2^{n + 2} + 1.

Only the first five Fermat numbers, k = 0, 1, 2, 3, 4 corresponding to 3, 5, 17, 257 and 65537 are known to be prime. All Fermat numbers from k = 5 to k = 32 are known to be composite. Fermat numbers till k = 11 are fully factorized.

Does there exist any squares of primes that divide Mersenne numbers of the form 2ⁿ − 1, for prime values of n? If such a prime exists, it must be a Wieferich prime, satisfying $2^{n-1} = 1\ (mod\ n^2)$. Only two such primes are known 1093 and 3511, out of a very deep search, and neither of these square divide a Mersenne number at all, for any prime value of n.

See also

• NFSNet
• NFS@Home

Further reading

• Cunningham, Allan J. C. & Woodall, H. J. (1925), Factorisation of y-n∓1, y=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers (n), London: Hodgson .

External links

• Website for the Cunningham project
• Website for the Brent-Montgomery-te Riele table
• Cunningham Tables