The Cunningham project

The Cunningham project is a project, started in 1925, to factor numbers of the form bⁿ ± 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:

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, b²ⁿ − 1 = (bⁿ − 1)(bⁿ + 1). Thus, when m divides n, b^m − 1 and b^m + 1 are factors of bⁿ − 1 if the quotient of n over m is even; only the first number is a factor if the quotient is odd. b^m + 1 is a factor of bⁿ − 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 = s² · 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}}.}$

Other factors[]

Once the algebraic and Aurifeuillian factors are removed, the other factors of bⁿ ± 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 bⁿ − 1 and b + 1 for bⁿ + 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 (bⁿ − 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 (bⁿ − 1)/(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 ≥ 2; these are the Mersenne numbers. Numbers of the form bⁿ + 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 2²ⁿ + 1 is of the form k2^n + 2 + 1.

Notation[]

bⁿ − 1 is denoted as b,n−. Similarly, bⁿ + 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,2ⁿ+; the number Aurifeuille factored in 1871 was the product of 2,58L and 2,58M.

See also[]

• Cunningham number
• ECMNET and NFS@Home, two collaborations working for the Cunningham project

References[]

External links[]

• Cunningham project homepage
• Brent-Montgomery-te Riele table (Cunningham tables for higher bases)
• Cunningham tables on Mersennewiki