The 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,
- [math]\displaystyle{ (b^{kn}-1) = (b^n-1) \sum _{r=0}^{k-1} b^{rn} }[/math]
for all k, and
- [math]\displaystyle{ (b^{kn}+1) = (b^n+1) \sum _{r=0}^{k-1} (-1)^r \cdot b^{rn} }[/math]
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,
- [math]\displaystyle{ b^n-1 = \prod _{d\mid n} \Phi_d(b) }[/math]
and
- [math]\displaystyle{ b^n+1 = \prod _{d\mid 2n, d!\mid n} \Phi_d(b) }[/math]
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 [math]\displaystyle{ \Phi_n(b) }[/math] have Aurifeuillian factorization.
- (i) [math]\displaystyle{ k\equiv 1 \mod 4 }[/math] and [math]\displaystyle{ n\equiv k \pmod{2k}; }[/math]
- (ii) [math]\displaystyle{ k\equiv 2, 3 \pmod 4 }[/math] and [math]\displaystyle{ n\equiv 2k \pmod{4k}. }[/math]
| 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 | A − B | 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 | A − B | 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 | A − B | 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 [math]\displaystyle{ \Phi_n(b) }[/math][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.
See also
- Cunningham number
- ECMNET and NFS@Home, two collaborations working for the Cunningham project
References
- ↑ Cunningham, Allan J. C.; Woodall, H. J. (1925). Factorisation of yn ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n. Hodgson.
- ↑ Brillhart, John; Lehmer, Derrick H.; Selfridge, John L.; Tuckerman, Bryant; Wagstaff, Samuel S. (2002). Factorizations of bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers. Contemporary Mathematics. 22. AMS. doi:10.1090/conm/022. ISBN 9780821850787.
- ↑ "The Cunningham Project". http://homes.cerias.purdue.edu/~ssw/cun/index.html. Retrieved 18 March 2012.
- ↑ "Main Cunningham Tables". https://homes.cerias.purdue.edu/~ssw/cun/pmain422.txt. Retrieved 24 June 2022. At the end of tables 2LM, 3+, 5-, 7+, 10+, 11+ and 12+ there are formulae detailing the Aurifeuillian factorisations.
- ↑ "Explanation of the notation on the Pages". http://homes.cerias.purdue.edu/~ssw/cun/notat. Retrieved 18 March 2012.
External links
- Cunningham project homepage
- Brent-Montgomery-te Riele table (Cunningham tables for higher bases)
- Cunningham tables on Prime Wiki
 |
