# The Cunningham project

(Redirected from Cunningham project)

The Cunningham project is a project, started in 1925, to factor numbers of the form bn ± 1 for b = 2, 3, 5, 6, 7, 10, 11, 12 and large n. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall.[1] There are three printed versions of the table, the most recent published in 2002,[2] as well as an online version.[3]

The current limits of the exponents are:

Base 2 3 5 6 7 10 11 12
Limit 1300 850 550 500 450 400 350 350
Aurifeuillian limit 2600 1700 1100 1000 900 800 700 700

## Factors of Cunningham numbers

Two types of factors can be derived from a Cunningham number without having to use a factorisation algorithm: algebraic factors, which depend on the exponent, and Aurifeuillian factors, which depend on both the base and the exponent.

### Algebraic factors

From elementary algebra,

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

for all k, and

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

for odd k. In addition, b2n − 1 = (bn − 1)(bn + 1). Thus, when m divides n, bm − 1 and bm + 1 are factors of bn − 1 if the quotient of n over m is even; only the first number is a factor if the quotient is odd. bm + 1 is a factor of bn − 1, if m divides n and the quotient is odd.

In fact,

${\displaystyle b^{n}-1=\prod _{d\mid n}\Phi _{d}(b)}$

and

${\displaystyle b^{n}+1=\prod _{d\mid 2n,d!\mid n}\Phi _{d}(b)}$

### Aurifeuillian factors

When the number is of a particular form (the exact expression varies with the base), Aurifeuillian factorization may be used, which gives a product of two or three numbers. The following equations give Aurifeuillian factors for the Cunningham project bases as a product of F, L and M:[4]

Let b = s2 · k with squarefree k, if one of the conditions holds, then ${\displaystyle \Phi _{n}(b)}$ have Aurifeuillian factorization.

(i) ${\displaystyle k\equiv 1\mod 4}$ and ${\displaystyle n\equiv k{\pmod {2k}};}$
(ii) ${\displaystyle k\equiv 2,3{\pmod {4}}}$ and ${\displaystyle n\equiv 2k{\pmod {4k}}.}$
b Number F L M Other definitions
2 24k + 2 + 1 1 22k + 1 − 2k + 1 + 1 22k + 1 + 2k + 1 + 1
3 36k + 3 + 1 32k + 1 + 1 32k + 1 − 3k + 1 + 1 32k + 1 + 3k + 1 + 1
5 510k + 5 − 1 52k + 1 − 1 T2 − 5k + 1T + 52k + 1 T2 + 5k + 1T + 52k + 1 T = 52k + 1 + 1
6 612k + 6 + 1 64k + 2 + 1 T2 − 6k + 1T + 62k + 1 T2 + 6k + 1T + 62k + 1 T = 62k + 1 + 1
7 714k + 7 + 1 72k + 1 + 1 AB A + B A = 76k + 3 + 3(74k + 2) + 3(72k + 1) + 1
B = 75k + 3 + 73k + 2 + 7k + 1
10 1020k + 10 + 1 104k + 2 + 1 AB A + B A = 108k + 4 + 5(106k + 3) + 7(104k + 2) + 5(102k + 1) + 1
B = 107k + 4 + 2(105k + 3) + 2(103k + 2) + 10k + 1
11 1122k + 11 + 1 112k + 1 + 1 AB A + B A = 1110k + 5 + 5(118k + 4) − 116k + 3 − 114k + 2 + 5(112k + 1) + 1
B = 119k + 5 + 117k + 4 − 115k + 3 + 113k + 2 + 11k + 1
12 126k + 3 + 1 122k + 1 + 1 122k + 1 − 6(12k) + 1 122k + 1 + 6(12k) + 1

### Other factors

Once the algebraic and Aurifeuillian factors are removed, the other factors of bn ± 1 are always of the form 2kn + 1, since they are all factors of ${\displaystyle \Phi _{n}(b)}$[citation needed]. When n is prime, both algebraic and Aurifeuillian factors are not possible, except the trivial factors (b − 1 for bn − 1 and b + 1 for bn + 1). For Mersenne numbers, the trivial factors are not possible for prime n, so all factors are of the form 2kn + 1. In general, all factors of (bn − 1)/(b − 1) are of the form 2kn + 1, where b ≥ 2 and n is prime, except when n divides b − 1, in which case (bn − 1)/(b − 1) is divisible by n itself.

Cunningham numbers of the form bn − 1 can only be prime if b = 2 and n is prime, assuming that n ≥ 2; these are the Mersenne numbers. Numbers of the form bn + 1 can only be prime if b is even and n is a power of 2, again assuming n ≥ 2; these are the generalized Fermat numbers, which are Fermat numbers when b = 2. Any factor of a Fermat number 22n + 1 is of the form k2n + 2 + 1.

## Notation

bn − 1 is denoted as b,n−. Similarly, bn + 1 is denoted as b,n+. When dealing with numbers of the form required for Aurifeuillian factorisation, b,nL and b,nM are used to denote L and M in the products above.[5] References to b,n− and b,n+ are to the number with all algebraic and Aurifeuillian factors removed. For example, Mersenne numbers are of the form 2,n− and Fermat numbers are of the form 2,2n+; the number Aurifeuille factored in 1871 was the product of 2,58L and 2,58M.