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 1200 800 500 450 400 400 350 300
Aurifeuillian limit 2400 1600 1000 900 800 800 700 600

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,

(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, 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.

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. If h = 2k − 1, the following equations give Aurifeuillian factors for the Cunningham project bases as a product of F, L and M:[4]

Base Number F L M Other definitions
2 22h + 1 1 2h − 2k + 1 2h + 2k + 1
3 33h + 1 3h + 1 3h − 3k + 1 3h + 3k + 1
5 55h − 1 5h − 1 T2 − 5kT + 5h T2 + 5kT + 5h T = 5h + 1
6 66h + 1 62h + 1 T2 − 6kT + 6h T2 + 6kT + 6h T = 6h + 1
7 77h + 1 7h + 1 T3B T3 + B T = 7h + 1
B = 7k(T2 − 7h)
10 1010h + 1 102h + 1 AB A + B A = 104h + 5(103h) + 7(102h) + 5(10h) + 1
B = 10k(103h + 2(102h) + 2(10h) + 1)
11 1111h + 1 11h + 1 AB A + B A = 115h + 5(114h) − 113h − 112h + 5(11h) + 1
B = 11k(114h + 113h − 112h + 11h + 1)
12 123h + 1 12h + 1 12h − 2h3k + 1 12h + 2h3k + 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. 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 22k + 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]