Login
Login

Cunningham Project

{{Short description|Mathematical project in integer factorization}}

The Cunningham Project is a collaborative effort 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.{{cite book|last=Cunningham|first=Allan J. C.|last2=Woodall|first2=H. J.|title=Factorization of yn ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n|publisher=Hodgson|year=1925}} There are three printed versions of the table, the most recent published in 2002,{{cite book|title=Factorizations of bn ± 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}} as well as an online version by Samuel Wagstaff.{{cite web|url=https://homes.cerias.purdue.edu/~ssw/cun/index.html|title=The Cunningham Project|accessdate=23 November 2023}}

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 (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=

{{main|Binomial number#Factorization}}

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, {{math|1=b2n − 1 = (bn − 1)(bn + 1)}}. Thus, when m divides n, {{math|1=bm − 1}} and {{math|1=bm + 1}} are factors of {{math|1=bn − 1}} if the quotient of n over m is even; only the first number is a factor if the quotient is odd. {{math|1=bm + 1}} is a factor of {{math|1=bn − 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 [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:{{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.

Let b = s2{{times}}k with squarefree k, if one of the conditions holds, then \Phi_n(b) have aurifeuillean factorization.

: (i) k\equiv 1 \pmod 4 and n\equiv k \pmod{2k};

: (ii) k\equiv 2, 3 \pmod 4 and n\equiv 2k \pmod{4k}.

{{table alignment}}

class="wikitable col2right col3right col4center col5center"

!b

!Number

!F

!L

!M

!Other definitions

2

|24k+2 + 1

|1

|22{{itco|k}}+1 − 2{{itco|k}}+1 + 1

|22{{itco|k}}+1 + 2{{itco|k}}+1 + 1

|

3

|36k+3 + 1

|32{{itco|k}}+1 + 1

|32{{itco|k}}+1 − 3{{itco|k}}+1 + 1

|32{{itco|k}}+1 + 3{{itco|k}}+1 + 1

|

5

|510k+5 − 1

|52{{itco|k}}+1 − 1

|{{itco|T}}2 − 5{{itco|k}}+1T + 52{{itco|k}}+1

|{{itco|T}}2 + 5{{itco|k}}+1T + 52{{itco|k}}+1

|T = 52{{itco|k}}+1 + 1

6

|612k+6 + 1

|64k+2 + 1

|{{itco|T}}2 − 6{{itco|k}}+1T + 62{{itco|k}}+1

|{{itco|T}}2 + 6{{itco|k}}+1T + 62{{itco|k}}+1

|T = 62{{itco|k}}+1 + 1

7

|714k+7 + 1

|72{{itco|k}}+1 + 1

|A − B

|A + B

|A = 76k+3 + 3(74k+2) + 3(72{{itco|k}}+1) + 1
B = 75k+3 + 73k+2 + 7{{itco|k}}+1

10

|1020{{itco|k}}+10 + 1

|104k+2 + 1

|A − B

|A + B

|A = 108k+4 + 5(106k+3) + 7(104k+2) + 5(102{{itco|k}}+1) + 1
B = 107k+4 + 2(105k+3) + 2(103k+2) + 10{{itco|k}}+1

11

|1122{{itco|k}}+11 + 1

|112{{itco|k}}+1 + 1

|A − B

|A + B

|A = 1110k+5 + 5(118k+4) − 116k+3 − 114k+2 + 5(112{{itco|k}}+1) + 1
B = 119k+5 + 117k+4 − 115k+3 + 113k+2 + 11{{itco|k}}+1

12

|126k+3 + 1

|122{{itco|k}}+1 + 1

|122{{itco|k}}+1 − 6(12k) + 1

|122{{itco|k}}+1 + 6(12k) + 1

|

=Other factors=

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

Cunningham numbers of the form {{math|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 {{math|bn + 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 numbers when b = 2. Any factor of a Fermat number {{math|22n + 1}} is of the form {{math|k·2n+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 aurifeuillean factorization, b,nL and b,nM are used to denote L and M in the products above.{{cite web|url=https://homes.cerias.purdue.edu/~ssw/cun/notat.txt|title=Explanation of the notation on the Pages|accessdate=23 November 2023}} 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,2n+; the number Aurifeuille factored in 1871 was the product of 2,58L and 2,58M.

See also

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 bn±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 bn±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 powers excluded, since a power of bn 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