Cunningham project

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Cunningham project is a project, 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.[1] There are three printed versions of the table, the most recent published in 2002,[2] as well as an online version.[3]

The current limits of the exponents are:

Base 2 3 5 6 7 10 11 12
Limit 1300 850 550 500 450 400 350 350
Aurifeuillian limit 2600 1700 1100 1000 900 800 700 700

Factors of Cunningham numbers[edit]

Two types of factors can be derived from a Cunningham number without having to use a factorisation algorithm: algebraic factors, which depend on the exponent, and Aurifeuillian factors, which depend on both the base and the exponent.

Algebraic factors[edit]

From elementary algebra,

for all k, and

for odd k. In addition, b2n − 1 = (bn − 1)(bn + 1). Thus, when m divides n, bm − 1 and bm + 1 are factors of bn − 1 if the quotient of n over m is even; only the first number is a factor if the quotient is odd. bm + 1 is a factor of bn − 1, if m divides n and the quotient is odd.

In fact,

and

Aurifeuillian factors[edit]

When the number is of a particular form (the exact expression varies with the base), Aurifeuillian factorization may be used, which gives a product of two or three numbers. The following equations give Aurifeuillian factors for the Cunningham project bases as a product of F, L and M:[4]

Let b = s2 * k with squarefree k, if one of the conditions holds, then have Aurifeuillian factorization.

(i) and
(ii) and
b Number F L M Other definitions
2 24k + 2 + 1 1 22k + 1 - 2k + 1 + 1 22k + 1 + 2k + 1 + 1
3 36k + 3 + 1 32k + 1 + 1 32k + 1 - 3k + 1 + 1 32k + 1 + 3k + 1 + 1
5 510k + 5 - 1 52k + 1 - 1 T2 - 5k + 1T + 52k + 1 T2 + 5k + 1T + 52k + 1 T = 52k + 1 + 1
6 612k + 6 + 1 64k + 2 + 1 T2 - 6'k + 1T + 62k + 1 T2 + 6k + 1T + 62k + 1 T = 62k + 1 + 1
7 714k + 7 + 1 72k + 1 + 1 A - B A + B A = 76k + 3 + 3(74k + 2) + 3(72k + 1) + 1
B = 75k + 3 + 73k + 2 + 7k + 1
10 1020k + 10 + 1 104k + 2 + 1 A - B A + B A = 108k + 4 + 5(106k + 3) + 7(104k + 2) + 5(102k + 1) + 1
B = 107k + 4 + 2(105k + 3) + 2(103k + 2) + 10k + 1
11 1122k + 11 + 1 112k + 1 + 1 A - B A + B A = 1110k + 5 + 5(118k + 4) - 116k + 3 - 114k + 2 + 5(112k + 1) + 1
B = 119k + 5 + 117k + 4 - 115k + 3 + 113k + 2 + 11k + 1
12 126k + 3 + 1 122k + 1 + 1 122k + 1 - 6(12k) + 1 122k + 1 + 6(12k) + 1

Other factors[edit]

Once the algebraic and Aurifeuillian factors are removed, the other factors of bn ± 1 are always of the form 2kn + 1, since they are all factors of [citation needed]. When n is prime, both algebraic and Aurifeuillian factors are not possible, except the trivial factors (b − 1 for bn − 1 and b + 1 for bn + 1). For Mersenne numbers, the trivial factors are not possible for prime n, so all factors are of the form 2kn + 1. In general, all factors of (bn − 1)/(b − 1) are of the form 2kn + 1, where b ≥ 2 and n is prime, except when n divides b − 1, in which case (bn − 1)/(b − 1) is divisible by n itself.

Cunningham numbers of the form 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 bn + 1 can only be prime if b is even and n is a power of 2, again assuming n ≥ 2; these are the generalized Fermat numbers, which are Fermat numbers when a = 1. Any factor of a Fermat number 22n + 1 is of the form k2n + 2 + 1.

Notation[edit]

bn − 1 is denoted as b,n−. Similarly, bn + 1 is denoted as b,n+. When dealing with numbers of the form required for Aurifeuillian factorisation, b,nL and b,nM are used to denote L and M in the products above.[5] References to b,n− and b,n+ are to the number with all algebraic and Aurifeuillian 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[edit]

References[edit]

  1. ^ Cunningham, Allan J. C.; Woodall, H. J. (1925). Factorisation of yn ± 1, y = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers n. Hodgson. 
  2. ^ Brillhart, John; Lehmer, Derrick H.; Selfridge, John L.; Tuckerman, Bryant; Wagstaff, Samuel S. (2002). "Factorizations of bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers". AMS. 
  3. ^ "The Cunningham Project". Retrieved 18 March 2012. 
  4. ^ "Main Cunningham Tables". Retrieved 18 March 2012.  At the end of tables 2LM, 3+, 5-, 7+, 10+, 11+ and 12+ are formulae detailing the Aurifeuillian factorisations.
  5. ^ "Explanation of the notation on the Pages". Retrieved 18 March 2012. 

External links[edit]