| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Cunningham project"
(restored) |
(upd. limits) |
||
| (8 intermediate revisions by 3 users not shown) | |||
| Line 4: | Line 4: | ||
The project started in 1925, when [[Allan Joseph Champneys Cunningham|Allan Cunningham]] and [[Herbert J. Woodall|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. | The project started in 1925, when [[Allan Joseph Champneys Cunningham|Allan Cunningham]] and [[Herbert J. Woodall|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 | + | 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 2023-04-20, see [https://homes.cerias.purdue.edu/~ssw/cun/pmain423.txt The Cunningham Project (main tables)]) of the exponents of the Cunningham tables are: |
| − | {| | + | {| class="wikitable" |
| − | + | ! Base | |
| + | | 2 || 3 || 5 || 6 || 7 || 10 || 11 || 12 | ||
|- | |- | ||
| − | | | + | ! Limit |
| + | | 1500 || 900 || 600 || 550 || 500 || 450 || 400 || 400 | ||
|} | |} | ||
| − | ==Properties of Cunningham | + | ==Properties of Cunningham factors== |
| − | In the Cunningham tables, we eliminate two types of factors before factoring the remaining cofactor. The first type is [[ | + | 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>b</math> and <math>n</math>. |
| − | ==Algebraic | + | ==Algebraic factorizations== |
It is trivial from elementary algebra that | It is trivial from elementary algebra that | ||
:<math>(b^{kn}-1) = (b^n-1) \sum _{r=0}^{k-1} b^{rn}</math> | :<math>(b^{kn}-1) = (b^n-1) \sum _{r=0}^{k-1} b^{rn}</math> | ||
| Line 28: | Line 30: | ||
Thus, it turns out that both <math>b^m-1</math> and <math>b^m+1</math> are factors of <math>b^n-1</math>, if <math>m</math> divides <math>n</math> and <math>n \over m</math> is even. Only <math>b^m-1</math> is a factor of <math>b^n-1</math>, if <math>m</math> divides <math>n</math> and <math>n \over m</math> is odd. Also, <math>b^m+1</math> is a factor of <math>b^n+1</math>, if <math>m</math> divides <math>n</math> and <math>n \over m</math> is odd. | Thus, it turns out that both <math>b^m-1</math> and <math>b^m+1</math> are factors of <math>b^n-1</math>, if <math>m</math> divides <math>n</math> and <math>n \over m</math> is even. Only <math>b^m-1</math> is a factor of <math>b^n-1</math>, if <math>m</math> divides <math>n</math> and <math>n \over m</math> is odd. Also, <math>b^m+1</math> is a factor of <math>b^n+1</math>, if <math>m</math> divides <math>n</math> and <math>n \over m</math> is odd. | ||
| − | ==Aurifeuillian | + | ==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+ | + | :<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 | + | :<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 | + | ::<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 | + | ::<math>M = 3^h + 3^k + 1</math> |
| − | :<math>7^{7h} + 1 = (7^h + 1).L.M</math> where <math>L = T^3 - B | + | <hr> |
| − | :<math>10^{10h} + 1 = (10^{2h} + 1).L.M</math> where <math>L = A - B | + | :<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 | + | ::<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 | + | ::<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 57: | Line 87: | ||
==See also== | ==See also== | ||
| − | *[[Cunningham | + | *[[Cunningham tables]] |
==External links== | ==External links== | ||
| 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] | ||
| − | *[ | + | *[[Wikipedia:Cunningham_project|Cunningham project]] |
| − | *[https:// | + | *[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)] |
| − | [[Category:Cunningham | + | *[https://www.mersenneforum.org/attachment.php?attachmentid=7727&d=1330555980 PDF of the third edition] |
| + | {{Navbox Projects}} | ||
| + | [[Category:Cunningham project| ]] | ||
Latest revision as of 23:48, 19 April 2023
Contents
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 2023-04-20, 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].
