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 (External links)
(table)
Line 7: Line 7:
  
 
Current limits of the exponents of the Cunningham tables are:
 
Current limits 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 || 1300 || 850 || 550 || 500 || 450 || 400 || 350 || 350
+
! Limit  
 +
| 1300 || 850 || 550 || 500 || 450 || 400 || 350 || 350
 
|}
 
|}
  
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.

Revision as of 08:02, 25 November 2019

The aim of this project is to find the complete factorization of numbers of the form bn±1 for b = 2, 3, 5, 6, 7, 10, 11, 12. The values of the exponent n 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 of the exponents of the Cunningham tables are:

Base 2 3 5 6 7 10 11 12
Limit 1300 850 550 500 450 400 350 350

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 b and n.

Algebraic factorizations

It is trivial from elementary algebra that

(bkn1)=(bn1)r=0k1brn

for any value of k and

(bkn+1)=(bn+1)r=0k1(1)k.brn

only when k is odd.

Also that,

(b2n1)=(bn1)(bn+1).

Thus, it turns out that both bm1 and bm+1 are factors of bn1, if m divides n and nm is even. Only bm1 is a factor of bn1, if m divides n and nm is odd. Also, bm+1 is a factor of bn+1, if m divides n and nm is odd.

Aurifeuillian factorizations

Consider the identity (h=2k1)

22h+1=L.M where L=2h2k+1, M=2h+2k+1

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.

33h+1=(3h+1).L.M where
L=3h3k+1
M=3h+3k+1

55h1=(5h1).L.M where
L=T2T.5k+5h
M=T2+T.5k+5h
T=5h+1

66h+1=(62h+1).L.M where
L=T2T.6k+6h
M=T2+T.6k+6h
T=6h+1

77h+1=(7h+1).L.M where
L=T3B
M=T3+B
T=7h+1
B=7k(T27h)

1010h+1=(102h+1).L.M where
L=AB
M=A+B
A=104h+5.103h+7.102h+5.10h+1
B=10k(103h+2.102h+2.10h+1)

1111h+1=(11h+1).L.M where
L=AB
M=A+B
A=115h+5.114h113h112h+5.11h+1
B=11k(114h+113h112h+11h+1)

123h+1=(12h+1).L.M where
L=12h2h.3k+1
M=12h+2h.3k+1

So, there exist an Aurifeuillian factorization for base b for any exponent of the form b(2k1) for integral values of k. 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 bn±1 will always be of the form 2kn+1. Note that when the exponent n is prime, algebraic and Aurifeuillian factors are not possible, except for the trivial factor of b1 for bn1 and b+1 for bn+1.

For Mersenne numbers of the form 2n1, even this trivial factor is not possible for prime values of n, so any factor of it should be of the form 2kn+1. In general, any factor of bn1b1 is of the form 2kn+1, b2 and n is prime, except when n is a factor of x1. In such cases, bn1b1 is divisible by n itself.

Cunningham numbers of the form bn1 can only be prime if b=2 and n is prime, assuming that n2, and numbers of the form bn+1 can only be prime if b is even and n is a power of 2, considering the fact that n2 again. Numbers of the form (2a)2k+1 are known as Generalized Fermat Numbers, which when a=1, are known as Fermat Numbers. In general, any factor of the Fermat Number 22k+1 is of the form k.2n+2+1.

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 2n1, for prime values of n? If such a prime exists, it must be a Wieferich prime, satisfying 2n1=1 (mod n2). 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 n.

See also

External links

Projects