Cunningham Project

The Cunningham Project is a collaborative effort 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 by Samuel Wagstaff.[3]

The current limits of the exponents are:

Base	2	3	5	6	7	10	11	12
Limit	1500	900	600	550	500	450	400	400
Aurifeuillean (LM) limit	3000	1800	1200	1100	1000	900	800	800

Factors of Cunningham number

Two types of factors can be derived from a Cunningham number without having to use a factorization algorithm: algebraic factors of binomial numbers (e.g. difference of two squares and sum of two cubes), which depend on the exponent, and aurifeuillean 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, 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,

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

and

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

See this page for more information.

Aurifeuillean factors

When the number is of a particular form (the exact expression varies with the base), aurifeuillean factorization may be used, which gives a product of two or three numbers. The following equations give aurifeuillean 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 $\Phi _{n}(b)$ have aurifeuillean 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	2^4k+2 + 1	1	2^2k +1 − 2^k +1 + 1	2^2k +1 + 2^k +1 + 1
3	3^6k+3 + 1	3^2k +1 + 1	3^2k +1 − 3^k +1 + 1	3^2k +1 + 3^k +1 + 1
5	5^10k+5 − 1	5^2k +1 − 1	T² − 5^k +1T + 5^2k +1	T² + 5^k +1T + 5^2k +1	T = 5^2k +1 + 1
6	6^12k+6 + 1	6^4k+2 + 1	T² − 6^k +1T + 6^2k +1	T² + 6^k +1T + 6^2k +1	T = 6^2k +1 + 1
7	7^14k+7 + 1	7^2k +1 + 1	A − B	A + B	A = 7^6k+3 + 3(7^4k+2) + 3(7^2k +1) + 1 B = 7^5k+3 + 7^3k+2 + 7^k +1
10	10^20k +10 + 1	10^4k+2 + 1	A − B	A + B	A = 10^8k+4 + 5(10^6k+3) + 7(10^4k+2) + 5(10^2k +1) + 1 B = 10^7k+4 + 2(10^5k+3) + 2(10^3k+2) + 10^k +1
11	11^22k +11 + 1	11^2k +1 + 1	A − B	A + B	A = 11^10k+5 + 5(11^8k+4) − 11^6k+3 − 11^4k+2 + 5(11^2k +1) + 1 B = 11^9k+5 + 11^7k+4 − 11^5k+3 + 11^3k+2 + 11^k +1
12	12^6k+3 + 1	12^2k +1 + 1	12^2k +1 − 6(12^k) + 1	12^2k +1 + 6(12^k) + 1

Other factors

Once the algebraic and aurifeuillean factors are removed, the other factors of bⁿ ± 1 are always of the form 2kn + 1, since they are all factors of $\Phi _{n}(b)$ . When n is prime, both algebraic and aurifeuillean 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^2ⁿ + 1 is of the form k2ⁿ⁺² + 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 aurifeuillean factorization, 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 aurifeuillean 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.

References

Cunningham, Allan J. C.; Woodall, H. J. (1925). Factorization of yⁿ ± 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 bⁿ ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers. Contemporary Mathematics. Vol. 22. AMS. doi:10.1090/conm/022. ISBN 9780821850787.
"The Cunningham Project". Retrieved 21 July 2023.
"Main Cunningham Tables". Retrieved 21 July 2023. At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ there are formulae detailing the aurifeuillean factorizations.
"Explanation of the notation on the Pages". Retrieved 21 July 2023.

External links

Cunningham project homepage
Factorizations of bⁿ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, second edition
Factorizations of bⁿ±1, b = 2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, third edition
Machine-readable Cunningham tables
The Cunningham Project
Brent-Montgomery-te Riele table (Cunningham tables for higher bases (bases 13 ≤ b ≤ 99, perfect powers excluded, since a power of bⁿ is also a power of b))
Online factor collection
Cunningham project on Prime Wiki
Cunningham project on PrimePages

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Cunningham, Allan J. C.; Woodall, H. J. (1925). Factorization of yⁿ ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n. Hodgson.

[2] Brillhart, John; Lehmer, Derrick H.; Selfridge, John L.; Tuckerman, Bryant; Wagstaff, Samuel S. (2002). Factorizations of bⁿ ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers. Contemporary Mathematics. Vol. 22. AMS. doi:10.1090/conm/022. ISBN 9780821850787.

[3] "The Cunningham Project". Retrieved 21 July 2023.

[4] "Main Cunningham Tables". Retrieved 21 July 2023. At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ there are formulae detailing the aurifeuillean factorizations.

[5] "Explanation of the notation on the Pages". Retrieved 21 July 2023.