Бүтін сандарды факторлау жобасы: Каннингем жобасы

Mathematical project in integer factorization
The Cunningham Project is a collaborative effort 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. There are three printed versions of the table, the most recent published in 2002, as well as an online version by Samuel Wagstaff. The current limits of the exponents are:
Base23567101112 Limit1500900600550500450400400Aurifeuillean (LM) limit30001800120011001000900800800

Two types of factors can be derived from a Cunningham number without having to use a factorization algorithm: algebraic factors of binomial numbers (e. g. difference of two squares and sum of two cubes), which depend on the exponent, and aurifeuillean factors, which depend on both the base and the exponent.

Once the algebraic and aurifeuillean factors are removed, the other factors of bn ± 1 are always of the form 2kn + 1, since they are all factors of When n is prime, both algebraic and aurifeuillean 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 b = 2. Any factor of a Fermat number 22n + 1 is of the form k2n+2 + 1.

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