Editing Cunningham Project

{{Short description|Mathematical project in integer factorization}}
The '''Cunningham Project''' is a collaborative effort started in 1925 to [[integer factorization|factor]] numbers of the form  ''b''<sup>''n''</sup> ± 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 [[H. J. Woodall|Herbert J. Woodall]].<ref>{{cite book|last=Cunningham|first=Allan J. C.|last2=Woodall|first2=H. J.|title=Factorization of y<sup>n</sup> ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n|publisher=Hodgson|year=1925}}</ref> There are three printed versions of the table, the most recent published in 2002,<ref>{{cite book|title=Factorizations of b<sup>n</sup> ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers|volume = 22|last1=Brillhart|first1=John|authorlink1=John Brillhart|last2=Lehmer|first2=Derrick H.|authorlink2=Derrick Henry Lehmer|last3=Selfridge|first3=John L.|authorlink3=John Selfridge|last4=Tuckerman|first4=Bryant|last5=Wagstaff|first5=Samuel S.|authorlink5=Samuel S. Wagstaff Jr.|publisher=AMS|year=2002|doi = 10.1090/conm/022|series = Contemporary Mathematics|isbn = 9780821850787}}</ref> as well as an online version by [[Samuel S. Wagstaff Jr.|Samuel Wagstaff]].<ref>{{cite web|url=https://homes.cerias.purdue.edu/~ssw/cun/index.html|title=The Cunningham Project|accessdate=23 November 2023}}</ref>

The current limits of the exponents are:
{| class="wikitable" style="text-align:center"
!Base
!2
!3
!5
!6
!7
!10
!11
!12 
|-
!Limit
|1500
|900
|600
|550
|500
|450
|400
|400
|-
![[Aurifeuillean factorization|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 [[Integer factorization#Factoring algorithms|factorization algorithm]]: [[algebra]]ic [[factorization|factors]] of [[binomial number]]s (e.g. [[difference of two squares]] and [[sum of two cubes]]), which depend on the exponent, and [[Aurifeuillean factorization|aurifeuillean factors]], which depend on both the base and the exponent.

===Algebraic factors===
{{main|Binomial number#Factorization}}
From elementary algebra,
:<math>(b^{kn}-1) = (b^n-1) \sum_{r=0}^{k-1} b^{rn}</math>
for all ''k'', and
:<math>(b^{kn}+1) = (b^n+1) \sum_{r=0}^{k-1} (-1)^r \cdot b^{rn}</math>
for [[parity (mathematics)|odd]] ''k''. In addition,  {{math|1=''b''<sup>2''n''</sup> − 1 = (''b''<sup>''n''</sup> − 1)(''b''<sup>''n''</sup> + 1)}}. Thus, when ''m'' [[divides]] ''n'', {{math|1=''b''<sup>''m''</sup> − 1}} and {{math|1=''b''<sup>''m''</sup> + 1}} are factors of {{math|1=''b''<sup>''n''</sup> − 1}} if the quotient of ''n'' over ''m'' is [[parity (mathematics)|even]]; only the first number is a factor if the quotient is odd. {{math|1=''b''<sup>''m''</sup> + 1}} is a factor of {{math|1=''b''<sup>''n''</sup> − 1}}, if ''m'' divides ''n'' and the quotient is odd.

In fact, 
:<math>b^n-1 = \prod_{d \mid n} \Phi_d(b)</math>
and
:<math>b^n+1 = \prod_{d \mid 2n,\, d \nmid n} \Phi_d(b)</math>

See [https://stdkmd.net/nrr/repunit/repunitnote.htm#repunit_factorization this page] for more information.

===Aurifeuillean factors===
{{main|Aurifeuillean factorization}}
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'':<ref>{{cite web|title=Main Cunningham Tables|url=https://homes.cerias.purdue.edu/~ssw/cun/pmain125.txt|accessdate=15 January 2025}} At the end of tables 2LM, 3+, 5-, 6+, 7+, 10+, 11+ and 12+ there are formulae detailing the aurifeuillean factorizations.</ref>

Let ''b'' = ''s''<sup>2</sup>{{times}}''k'' with [[squarefree]] ''k'', if one of the conditions holds, then <math>\Phi_n(b)</math> have aurifeuillean factorization.
: (i) <math>k\equiv 1 \pmod 4</math> and <math>n\equiv k \pmod{2k};</math>
: (ii) <math>k\equiv 2, 3 \pmod 4</math> and <math>n\equiv 2k \pmod{4k}.</math>
{{table alignment}}
{| class="wikitable col2right col3right col4center col5center"
!''b''
!Number
!''F''
!''L''
!''M''
!Other definitions
|-
!2
|2<sup>4''k''+2</sup> + 1
|1
|2<sup>2{{itco|''k''}}+1</sup> − 2<sup>{{itco|''k''}}+1</sup> + 1
|2<sup>2{{itco|''k''}}+1</sup> + 2<sup>{{itco|''k''}}+1</sup> + 1
|
|-
!3
|3<sup>6''k''+3</sup> + 1
|3<sup>2{{itco|''k''}}+1</sup> + 1
|3<sup>2{{itco|''k''}}+1</sup> − 3<sup>{{itco|''k''}}+1</sup> + 1
|3<sup>2{{itco|''k''}}+1</sup> + 3<sup>{{itco|''k''}}+1</sup> + 1
|
|-
!5
|5<sup>10''k''+5</sup> − 1
|5<sup>2{{itco|''k''}}+1</sup> − 1
|{{itco|''T''}}<sup>2</sup> − 5<sup>{{itco|''k''}}+1</sup>''T'' + 5<sup>2{{itco|''k''}}+1</sup>
|{{itco|''T''}}<sup>2</sup> + 5<sup>{{itco|''k''}}+1</sup>''T'' + 5<sup>2{{itco|''k''}}+1</sup>
|''T'' = 5<sup>2{{itco|''k''}}+1</sup> + 1
|-
!6
|6<sup>12''k''+6</sup> + 1
|6<sup>4''k''+2</sup> + 1
|{{itco|''T''}}<sup>2</sup> − 6<sup>{{itco|''k''}}+1</sup>''T'' + 6<sup>2{{itco|''k''}}+1</sup>
|{{itco|''T''}}<sup>2</sup> + 6<sup>{{itco|''k''}}+1</sup>''T'' + 6<sup>2{{itco|''k''}}+1</sup>
|''T'' = 6<sup>2{{itco|''k''}}+1</sup> + 1
|-
!7
|7<sup>14''k''+7</sup> + 1
|7<sup>2{{itco|''k''}}+1</sup> + 1
|''A'' − ''B''
|''A'' + ''B''
|''A'' = 7<sup>6''k''+3</sup> + 3(7<sup>4''k''+2</sup>) + 3(7<sup>2{{itco|''k''}}+1</sup>) + 1<br/>''B'' = 7<sup>5''k''+3</sup> + 7<sup>3''k''+2</sup> + 7<sup>{{itco|''k''}}+1</sup>
|-
!10
|10<sup>20{{itco|''k''}}+10</sup> + 1
|10<sup>4''k''+2</sup> + 1
|''A'' − ''B''
|''A'' + ''B''
|''A'' = 10<sup>8''k''+4</sup> + 5(10<sup>6''k''+3</sup>) + 7(10<sup>4''k''+2</sup>) + 5(10<sup>2{{itco|''k''}}+1</sup>) + 1<br/>''B'' = 10<sup>7''k''+4</sup> + 2(10<sup>5''k''+3</sup>) + 2(10<sup>3''k''+2</sup>) + 10<sup>{{itco|''k''}}+1</sup>
|-
!11
|11<sup>22{{itco|''k''}}+11</sup> + 1
|11<sup>2{{itco|''k''}}+1</sup> + 1
|''A'' − ''B''
|''A'' + ''B''
|''A'' = 11<sup>10''k''+5</sup> + 5(11<sup>8''k''+4</sup>) − 11<sup>6''k''+3</sup> − 11<sup>4''k''+2</sup> + 5(11<sup>2{{itco|''k''}}+1</sup>) + 1<br/>''B'' = 11<sup>9''k''+5</sup> + 11<sup>7''k''+4</sup> − 11<sup>5''k''+3</sup> + 11<sup>3''k''+2</sup> + 11<sup>{{itco|''k''}}+1</sup>
|-
!12
|12<sup>6''k''+3</sup> + 1
|12<sup>2{{itco|''k''}}+1</sup> + 1
|12<sup>2{{itco|''k''}}+1</sup> − 6(12<sup>''k''</sup>) + 1
|12<sup>2{{itco|''k''}}+1</sup> + 6(12<sup>''k''</sup>) + 1
|
|}

===Other factors===
Once the algebraic and aurifeuillean factors are removed, the other factors of {{math|''b''<sup>''n''</sup> ± 1}} are always of the form {{math|2''kn'' + 1}}, since the factors of {{math|''b''<sup>''n''</sup> − 1}} are all factors of <math>\Phi_n(b)</math>, and the factors of {{math|''b''<sup>''n''</sup> + 1}} are all factors of <math>\Phi_{2n}(b)</math>. When ''n'' is [[prime number|prime]], both algebraic and aurifeuillean factors are not possible, except the trivial factors ({{math|''b'' − 1}} for {{math|''b''<sup>''n''</sup> − 1}} and {{math|''b'' + 1}} for {{math|''b''<sup>''n''</sup> + 1}}). For [[Mersenne numbers]], the trivial factors are not possible for {{nowrap|prime ''n''}}, so all factors are of the form {{math|2''kn'' + 1}}. In general, all factors of {{math|(''b''<sup>''n''</sup> − 1)&hairsp;/(''b'' − 1)}} are of the form {{math|2''kn'' + 1,}} where {{math|''b'' ≥ 2}} and ''n'' is prime, except when ''n'' divides {{math|''b'' − 1}}, in which case {{math|(''b''<sup>''n''</sup> − 1)&hairsp;/(''b'' − 1)}} is divisible by ''n'' itself.

Cunningham numbers of the form {{math|''b''<sup>''n''</sup> − 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 {{math|''b''<sup>''n''</sup> + 1}} can only be prime if ''b'' is even and ''n'' is a [[power of 2]], again assuming {{math|''n'' ≥ 2;}} these are the generalized Fermat numbers, which are [[Fermat number]]s when ''b'' = 2. Any factor of a Fermat number {{math|2<sup>2<sup>''n''</sup></sup> + 1}} is of the form {{math|''k''&middot;2<sup>''n''+2</sup> + 1}}.

==Notation==
''b''<sup>''n''</sup>&nbsp;−&nbsp;1 is denoted as ''b'',''n''−. Similarly, ''b''<sup>''n''</sup>&nbsp;+&nbsp;1 is denoted as ''b'',''n''+. When dealing with numbers of the form required for aurifeuillean factorization, ''b'',''n''L and ''b'',''n''M are used to denote L and M in [[Cunningham project#Aurifeuillean factors|the products above]].<ref>{{cite web|url=https://homes.cerias.purdue.edu/~ssw/cun/notat.txt|title=Explanation of the notation on the Pages|accessdate=23 November 2023}}</ref> 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<sup>''n''</sup>+; the number [[Léon-François-Antoine Aurifeuille|Aurifeuille]] factored in 1871 was the product of 2,58L and&nbsp;2,58M.

==See also==
*[[Cunningham number]]
*[[Lenstra elliptic curve factorization#External links|ECMNET]] and [[NFSNET|NFS@Home]], two collaborations working for the Cunningham project

==References==
{{reflist}}

==External links==
*[https://homes.cerias.purdue.edu/~ssw/cun/index.html Cunningham project homepage]
*[https://doi.org/10.1090/conm/022 Factorizations of ''b''<sup>''n''</sup>±1, ''b'' = 2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, second edition]
*[https://web.archive.org/web/20061008124709/http://www.ams.org/online_bks/conm22/conm22-whole.pdf Factorizations of ''b''<sup>''n''</sup>±1, ''b'' = 2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, third edition]
*[https://homes.cerias.purdue.edu/~ssw/cun/pmain125.txt Main table of The Cunningham project]
*[https://homes.cerias.purdue.edu/~ssw/cun/cun.html Older main table of The Cunningham project]
*[https://homes.cerias.purdue.edu/~ssw/cun/third/pmain901 Main table of The third edition of the Cunningham book]
*[https://web.archive.org/web/20190315214330/http://cage.ugent.be/~jdemeyer/cunningham/ Machine-readable Cunningham tables]
*[https://homes.cerias.purdue.edu/~ssw/cun1.pdf The Cunningham Project]
*[https://maths-people.anu.edu.au/~brent/factors.html Brent-Montgomery-te Riele table] (Cunningham tables for higher bases (bases 13 ≤ ''b'' ≤ 99, [[perfect power]]s excluded, since a power of ''b''<sup>''n''</sup> is also a power of ''b''))
*[http://myfactors.mooo.com/ Online factor collection]
*[https://rieselprime.de/ziki/Cunningham_project Cunningham project] on Prime Wiki
*[https://t5k.org/glossary/xpage/CunninghamProject.html Cunningham project] on [[PrimePages]]

[[Category:Number theory]]