Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
Navigation
Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

Difference between revisions of "Cunningham project"

From Prime-Wiki
Jump to: navigation, search
m
(update date & link for main tables)
 
(8 intermediate revisions by 3 users not shown)
Line 6: Line 6:
 
At this moment three editions of the book about the Cunningham project have been published.
 
At this moment three editions of the book about the Cunningham project have been published.
  
−
Current limits of the exponents of the Cunningham tables are:
+
Current limits (as of 2024-05-23, see [https://homes.cerias.purdue.edu/~ssw/cun/pmain524.txt The Cunningham Project (main tables)]) of the exponents of the Cunningham tables are:
−
{| border=\"1\" cellpadding=\"4px\" style=\"border:3px; border-color:#000;border-collapse:collapse;\"
+
{| class="wikitable"
−
| style=\"background-color:#CCC\"| Base || 2 || 3 || 5 || 6 || 7 || 10 || 11 || 12
+
! Base
 +
| 2 || 3 || 5 || 6 || 7 || 10 || 11 || 12
 
|-
 
|-
−
| style=\"background-color:#CCC\"| Limit || 1200 || 600 || 450 || 400 || 400 || 400 || 300 || 300
+
! Limit
 +
| 1500 || 900 || 600 || 550 || 500 || 450 || 400 || 400
 
|}
 
|}
  
Line 29: Line 31:
  
 
==Aurifeuillian factorizations==
 
==Aurifeuillian factorizations==
−
Consider the identity
+
Consider the identity (<math>h = 2k-1</math>)
−
:<math>2^{2h}+1 = L.M</math> where <math>L = 2^h-2^k+1,\ M = 2^h+2^k+1,\ h = 2k-1</math>
+
:<math>2^{2h}+1 = L.M</math> where <math>L = 2^h-2^k+1,\ M = 2^h+2^k+1</math>
  
 
This factorization was discovered for one value by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases.
 
This factorization was discovered for one value by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases.
  
−
:<math>3^{3h} + 1 = (3^h + 1).L.M</math> where <math>L = 3^h - 3^k + 1,\ M = 3^h + 3^k + 1,\ h = 2k - 1</math>
+
:<math>3^{3h} + 1 = (3^h + 1).L.M</math> where
−
:<math>5^{5h} - 1 = (5h - 1).L.M</math> where <math>L = T^2 - T.5^k + 5^h,\ M = T^2 + T.5^k + 5^h,\ T = 5^h + 1,\ h = 2k - 1</math>
+
::<math>L = 3^h - 3^k + 1</math>
−
:<math>6^{6h} + 1 = (6^{2h} + 1).L.M</math> where <math>L = T^2 - T.6^k + 6^h,\ M = T^2 + T.6^k + 6^h,\ T = 6^h + 1,\ h = 2k - 1</math>
+
::<math>M = 3^h + 3^k + 1</math>
−
:<math>7^{7h} + 1 = (7^h + 1).L.M</math> where <math>L = T^3 - B,\ M = T^3 + B,\ T = 7^h + 1,\ B = 7^k(T^2 - 7^h),\ h = 2k - 1</math>
+
<hr>
−
:<math>10^{10h} + 1 = (10^{2h} + 1).L.M</math> where <math>L = A - B,\ M = A + B,\ A = 10^{4h} + 5.10^{3h} + 7.10^{2h} + 5.10^h + 1,\ B = 10^k(10^{3h} + 2.10^{2h} + 2.10^h + 1),\ h = 2k - 1</math>
+
:<math>5^{5h} - 1 = (5h - 1).L.M</math> where
−
:<math>11^{11h} + 1 = (11^h + 1).L.M</math> where <math>L = A - B,\ M = A + B,\ A = 11^{5h} + 5.11^{4h} - 11^{3h} - 11^{2h} + 5.11^h + 1,\ B = 11^k(11^{4h} + 11^{3h} - 11^{2h} + 11^h + 1),\ h = 2k - 1</math>
+
::<math>L = T^2 - T.5^k + 5^h</math>
−
:<math>12^{3h} + 1 = (12^h + 1).L.M</math> where <math>L = 12^h - 2^h.3^k + 1,\ M = 12^h + 2^h.3^k + 1,\ h = 2k - 1</math>
+
::<math>M = T^2 + T.5^k + 5^h</math>
 +
:::<math>T = 5^h + 1</math>
 +
<hr>
 +
:<math>6^{6h} + 1 = (6^{2h} + 1).L.M</math> where
 +
::<math>L = T^2 - T.6^k + 6^h</math>
 +
::<math>M = T^2 + T.6^k + 6^h</math>
 +
:::<math>T = 6^h + 1</math>
 +
<hr>
 +
:<math>7^{7h} + 1 = (7^h + 1).L.M</math> where
 +
::<math>L = T^3 - B</math>
 +
::<math>M = T^3 + B</math>
 +
:::<math>T = 7^h + 1</math>
 +
:::<math>B = 7^k(T^2 - 7^h)</math>
 +
<hr>
 +
:<math>10^{10h} + 1 = (10^{2h} + 1).L.M</math> where
 +
::<math>L = A - B</math>
 +
::<math>M = A + B</math>
 +
:::<math>A = 10^{4h} + 5.10^{3h} + 7.10^{2h} + 5.10^h + 1</math>
 +
:::<math>B = 10^k(10^{3h} + 2.10^{2h} + 2.10^h + 1)</math>
 +
<hr>
 +
:<math>11^{11h} + 1 = (11^h + 1).L.M</math> where
 +
::<math>L = A - B</math>
 +
::<math>M = A + B</math>
 +
:::<math>A = 11^{5h} + 5.11^{4h} - 11^{3h} - 11^{2h} + 5.11^h + 1</math>
 +
:::<math>B = 11^k(11^{4h} + 11^{3h} - 11^{2h} + 11^h + 1)</math>
 +
<hr>
 +
:<math>12^{3h} + 1 = (12^h + 1).L.M</math> where
 +
::<math>L = 12^h - 2^h.3^k + 1</math>
 +
::<math>M = 12^h + 2^h.3^k + 1</math>
  
 
So, there exist an Aurifeuillian factorization for base <math>b</math> for any exponent of the form <math>b(2k-1)</math> for integral values of <math>k</math>. Note that the Aurifeuillian factorization of base 5 is on the negative side, while for the other bases 2, 3, 6, 7, 10, 11, 12 it is on the positive side.
 
So, there exist an Aurifeuillian factorization for base <math>b</math> for any exponent of the form <math>b(2k-1)</math> for integral values of <math>k</math>. Note that the Aurifeuillian factorization of base 5 is on the negative side, while for the other bases 2, 3, 6, 7, 10, 11, 12 it is on the positive side.
Line 63: Line 93:
 
*[http://wwwmaths.anu.edu.au/~brent/factors.html Brent-Montgomery-te Riele table Web site] (extension to larger bases).
 
*[http://wwwmaths.anu.edu.au/~brent/factors.html Brent-Montgomery-te Riele table Web site] (extension to larger bases).
 
*[http://www.mersenneforum.org/forumdisplay.php?f=51 Cunningham tables at MersenneForum]
 
*[http://www.mersenneforum.org/forumdisplay.php?f=51 Cunningham tables at MersenneForum]
−
*[http://www.ams.org/online_bks/conm22/ Online version of the third edition of the book]
 
 
*[[Wikipedia:Cunningham_project|Cunningham project]]
 
*[[Wikipedia:Cunningham_project|Cunningham project]]
−
[[Category:Cunningham project]]
+
*[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 (includes PDF download link)]
 +
*[https://www.mersenneforum.org/attachment.php?attachmentid=7727&d=1330555980 PDF of the third edition]
 +
{{Navbox Projects}}
 +
[[Category:Cunningham project| ]]

Latest revision as of 05:23, 7 June 2024

The aim of this project is to find the complete factorization of numbers of the form [math]\displaystyle{ b^n\pm 1 }[/math] for [math]\displaystyle{ b }[/math] = 2, 3, 5, 6, 7, 10, 11, 12. The values of the exponent [math]\displaystyle{ n }[/math] are selected so there is never too many factorizations left. This means that when the supply of numbers to be factored is low, the project starts factoring numbers with higher exponents, tracking the advances in factorization algorithms and speed of computers.

The project started in 1925, when Allan Cunningham and Herbert Woodall published a book of tables about this subject. Many people contributed to it and it is considered the oldest continuously ongoing activity in computational number theory.

At this moment three editions of the book about the Cunningham project have been published.

Current limits (as of 2024-05-23, see The Cunningham Project (main tables)) of the exponents of the Cunningham tables are:

Base 2 3 5 6 7 10 11 12
Limit 1500 900 600 550 500 450 400 400

Properties of Cunningham factors

In the Cunningham tables, we eliminate two types of factors before factoring the remaining cofactor. The first type is algebraic factor, which are derived from a lower exponent. The second type is aurifeuillian factor, in which the whole number can be split into two parts directly, for certain combination of values of [math]\displaystyle{ b }[/math] and [math]\displaystyle{ n }[/math].

Algebraic factorizations

It is trivial from elementary algebra that

[math]\displaystyle{ (b^{kn}-1) = (b^n-1) \sum _{r=0}^{k-1} b^{rn} }[/math]

for any value of [math]\displaystyle{ k }[/math] and

[math]\displaystyle{ (b^{kn}+1) = (b^n+1) \sum _{r=0}^{k-1} (-1)^k.b^{rn} }[/math]

only when [math]\displaystyle{ k }[/math] is odd.

Also that,

[math]\displaystyle{ (b^{2n}-1) = (b^n-1)(b^n+1) }[/math].

Thus, it turns out that both [math]\displaystyle{ b^m-1 }[/math] and [math]\displaystyle{ b^m+1 }[/math] are factors of [math]\displaystyle{ b^n-1 }[/math], if [math]\displaystyle{ m }[/math] divides [math]\displaystyle{ n }[/math] and [math]\displaystyle{ n \over m }[/math] is even. Only [math]\displaystyle{ b^m-1 }[/math] is a factor of [math]\displaystyle{ b^n-1 }[/math], if [math]\displaystyle{ m }[/math] divides [math]\displaystyle{ n }[/math] and [math]\displaystyle{ n \over m }[/math] is odd. Also, [math]\displaystyle{ b^m+1 }[/math] is a factor of [math]\displaystyle{ b^n+1 }[/math], if [math]\displaystyle{ m }[/math] divides [math]\displaystyle{ n }[/math] and [math]\displaystyle{ n \over m }[/math] is odd.

Aurifeuillian factorizations

Consider the identity ([math]\displaystyle{ h = 2k-1 }[/math])

[math]\displaystyle{ 2^{2h}+1 = L.M }[/math] where [math]\displaystyle{ L = 2^h-2^k+1,\ M = 2^h+2^k+1 }[/math]

This factorization was discovered for one value by Aurifeuille and the general form was subsequently given by Lucas. Here are the Aurifeuillian factorizations for the other bases.

[math]\displaystyle{ 3^{3h} + 1 = (3^h + 1).L.M }[/math] where
[math]\displaystyle{ L = 3^h - 3^k + 1 }[/math]
[math]\displaystyle{ M = 3^h + 3^k + 1 }[/math]
[math]\displaystyle{ 5^{5h} - 1 = (5h - 1).L.M }[/math] where
[math]\displaystyle{ L = T^2 - T.5^k + 5^h }[/math]
[math]\displaystyle{ M = T^2 + T.5^k + 5^h }[/math]
[math]\displaystyle{ T = 5^h + 1 }[/math]
[math]\displaystyle{ 6^{6h} + 1 = (6^{2h} + 1).L.M }[/math] where
[math]\displaystyle{ L = T^2 - T.6^k + 6^h }[/math]
[math]\displaystyle{ M = T^2 + T.6^k + 6^h }[/math]
[math]\displaystyle{ T = 6^h + 1 }[/math]
[math]\displaystyle{ 7^{7h} + 1 = (7^h + 1).L.M }[/math] where
[math]\displaystyle{ L = T^3 - B }[/math]
[math]\displaystyle{ M = T^3 + B }[/math]
[math]\displaystyle{ T = 7^h + 1 }[/math]
[math]\displaystyle{ B = 7^k(T^2 - 7^h) }[/math]
[math]\displaystyle{ 10^{10h} + 1 = (10^{2h} + 1).L.M }[/math] where
[math]\displaystyle{ L = A - B }[/math]
[math]\displaystyle{ M = A + B }[/math]
[math]\displaystyle{ A = 10^{4h} + 5.10^{3h} + 7.10^{2h} + 5.10^h + 1 }[/math]
[math]\displaystyle{ B = 10^k(10^{3h} + 2.10^{2h} + 2.10^h + 1) }[/math]
[math]\displaystyle{ 11^{11h} + 1 = (11^h + 1).L.M }[/math] where
[math]\displaystyle{ L = A - B }[/math]
[math]\displaystyle{ M = A + B }[/math]
[math]\displaystyle{ A = 11^{5h} + 5.11^{4h} - 11^{3h} - 11^{2h} + 5.11^h + 1 }[/math]
[math]\displaystyle{ B = 11^k(11^{4h} + 11^{3h} - 11^{2h} + 11^h + 1) }[/math]
[math]\displaystyle{ 12^{3h} + 1 = (12^h + 1).L.M }[/math] where
[math]\displaystyle{ L = 12^h - 2^h.3^k + 1 }[/math]
[math]\displaystyle{ M = 12^h + 2^h.3^k + 1 }[/math]

So, there exist an Aurifeuillian factorization for base [math]\displaystyle{ b }[/math] for any exponent of the form [math]\displaystyle{ b(2k-1) }[/math] for integral values of [math]\displaystyle{ k }[/math]. Note that the Aurifeuillian factorization of base 5 is on the negative side, while for the other bases 2, 3, 6, 7, 10, 11, 12 it is on the positive side.

Other factors

Once the algebraic and Aurifeuillian factors are removed, the other factors of [math]\displaystyle{ b^n \pm 1 }[/math] will always be of the form [math]\displaystyle{ 2kn+1 }[/math]. Note that when the exponent [math]\displaystyle{ n }[/math] is prime, algebraic and Aurifeuillian factors are not possible, except for the trivial factor of [math]\displaystyle{ b-1 }[/math] for [math]\displaystyle{ b^n-1 }[/math] and [math]\displaystyle{ b+1 }[/math] for [math]\displaystyle{ b^n+1 }[/math].

For Mersenne numbers of the form [math]\displaystyle{ 2^n-1 }[/math], even this trivial factor is not possible for prime values of [math]\displaystyle{ n }[/math], so any factor of it should be of the form [math]\displaystyle{ 2kn+1 }[/math]. In general, any factor of [math]\displaystyle{ b^n-1 \over b-1 }[/math] is of the form [math]\displaystyle{ 2kn+1 }[/math], [math]\displaystyle{ b \ge 2 }[/math] and [math]\displaystyle{ n }[/math] is prime, except when [math]\displaystyle{ n }[/math] is a factor of [math]\displaystyle{ x-1 }[/math]. In such cases, [math]\displaystyle{ b^n-1 \over b-1 }[/math] is divisible by [math]\displaystyle{ n }[/math] itself.

Cunningham numbers of the form [math]\displaystyle{ b^n-1 }[/math] can only be prime if [math]\displaystyle{ b=2 }[/math] and [math]\displaystyle{ n }[/math] is prime, assuming that [math]\displaystyle{ n \ge 2 }[/math], and numbers of the form [math]\displaystyle{ b^n+1 }[/math] can only be prime if [math]\displaystyle{ b }[/math] is even and [math]\displaystyle{ n }[/math] is a power of 2, considering the fact that [math]\displaystyle{ n \ge 2 }[/math] again. Numbers of the form [math]\displaystyle{ (2a)^{2^k}+1 }[/math] are known as Generalized Fermat Numbers, which when [math]\displaystyle{ a = 1 }[/math], are known as Fermat Numbers. In general, any factor of the Fermat Number [math]\displaystyle{ 2^{2^k}+1 }[/math] is of the form [math]\displaystyle{ k.2^{n+2}+1 }[/math].

Only the first five Fermat numbers, k = 0, 1, 2, 3, 4 corresponding to 3, 5, 17, 257 and 65537 are known to be prime. All Fermat numbers from k = 5 to k = 32 are known to be composite. Fermat numbers till k = 11 are fully factorized.

Does there exist any squares of primes that divide Mersenne numbers of the form [math]\displaystyle{ 2^n-1 }[/math], for prime values of [math]\displaystyle{ n }[/math]? If such a prime exists, it must be a Wieferich prime, satisfying [math]\displaystyle{ 2^{n-1} = 1\ (mod\ n^2) }[/math]. Only two such primes are known 1093 and 3511, out of a very deep search, and neither of these square divide a Mersenne number at all, for any prime value of [math]\displaystyle{ n }[/math].

See also

External links

Projects
Retrieved from "https://www.rieselprime.de/z/index.php?title=Cunningham_project&oldid=32931"