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,
\( (b^{{kn}}-1)=(b^{n}-1)\sum _{{r=0}}^{{k-1}}b^{{rn}} \)
for all k, and
\( (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
Main article: Aurifeuillian factorization
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 \( \Phi _{n}(b) \) have Aurifeuillian factorization.
(i) \( k\equiv 1\mod 4 \) and \( n\equiv k{\pmod {2k}}; \)
(ii) \( k\equiv 2,3{\pmod 4} \) and \( 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 | 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 \( \Phi _{n}(b) \) ]. 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". Retrieved 18 March 2012.
"Main Cunningham Tables". Archived from the original on 15 April 2012. Retrieved 18 March 2012. At the end of tables 2LM, 3+, 5−, 7+, 10+, 11+ and 12+ are formulae detailing the Aurifeuillian factorisations.
"Explanation of the notation on the Pages". Retrieved 18 March 2012.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
