The Cunningham Project is an long running endeavour to factorise numbers of the form bn ± 1 for b=2, 3, 5, 6, 7, 10, 11, 12, up to high powers of n. It started in 1925, long before the electronic computer age. The collection of factors from scattered source and the collation and verification of the factors was a difficult challenge at the time.
At that time a computer was the name given to "a person that computed". These days most people know a computer as the box that sits on their desk in the study. Most people will reach for a calculator once their numbers go into double figures and are unlikely to ever experience the pleasure and sense of accomplishment the hand calculator would derive from factoring a large number.
On the other hand, more time can be spent on the development of factoring algorithms and less time on the drudgery of hand multiplication and division. This has led to the invention of many high powered primality/factoring algorithms and methods that more fully utilise the computer power available today on the desktop. With the improvement from two directions at once, the factorisation of these large numbers has grown in leaps and bounds.
I stumbled across the The Cunningham Project Site one day and was pleasantly surprised what I discovered there. There are several up to date Cunningham factorisation tables provided. They are organised into three files:
- The main table of factors pmain*.txt for C±(b,n). In this table large primes and composite cofactors are aliased as Pn and Cn where n denotes the length of the decimal expansion of the number.
- Appendix appa*.txt, a table of the full decimal expansion of the Pn's.
- Appendix appc*.txt, a table of the full decimal expansion of the Cn's. These numbers are the unfactored composite cofactors. They are known to be composite, but no factors are yet known.
- The * above is a short date - currently it is 1104 denoting November, 2004.
The site also has "wanted lists" for the composite cofactors whose factorisation is considered most desirable. These are usually the smallest Cn in each table. There is a page of latest developments containing factors not yet added to the above 3 text files and even a slow factor calculator for factoring a single Cunningham number at a time. They also include a link to Factorizations of b^n+-1, b=2,3,5,6,7,10,11,12 Up to High Powers. At this site you can obtain free of cost, a full PDF copy of the book.
This book is an excellent resource with detailed explanation on how to read the tables and use them to manually generate other factors not explicitly tabled - for instance Aurifeuillian factorisation and the factorisation of C−(b,n) for even n.
There is also a discussion of the development and history of factoring techniques and primality tests from the start of the project in 1925 right up to the current day. Primality proof summaries are given and a list of 348 references to key papers in the area of factorisation/primality.
To facilitate my understanding Cunningham numbers and their factorisation I decided to write a program that would read in all the table data and generate all the factors for each base b and exponent n. I wanted to see the full factorisations in place without having to look to earlier exponents for factors. In the published tables all references to unfactored composites and primes in any given factorisation need to be looked up in separate appendices. They don't provide factorisations for even exponents. I don't see why even exponents are any different than odd composite exponents, both can be algebraically factored. While the prime exponent cases are the most interesting (and difficult) to factor, I see no reason not to include all the factorisations for easy reference.
In their original state, the tables are not exactly computer friendly so I decided that some preprocessing of the data to a more rigid record based format more was in order prior to loading into my program.
Just for fun I decided the program should generate both the standard text based output plus a more interesting HTML format with some hyperlinking and colour coding to move between the factors and spot primes and composite cofactors.
This program reads preprocessed Cunningham Database files of factored Cunningham numbers and produces both text files and HTML files of complete factorisations - all factors are produced in "all their deserved glory".
My implementation is not completely straightforward. There are some interesting use of data structures, in particular a linked list for the main factor table with dynamic memory allocation used for factor and exponent strings. The alternative of using static structures would have been very wasteful due to the huge variation in sizes of factors (as small as 1 digit, as large as 200+ digits).
The data/process flow is as follows (change MMYY to the appropriate short date)
- Preprocess pmain<date>.txt using the command line "awk -f pmain.awk pmainMMYY.txt > pmain.in"
- Preprocess appaMMYY.txt using the command line "awk -f appa.awk appaMMYY.txt > appa.in"
- Preprocess appcMMYY.txt using the command line "awk -f appc.awk appcMMYY.txt > appc.in"
- Modify html_header.txt to suit (the HTML wrapper).
- Compile, link and run this C program.
- Have look at the 16 text file and 16 HTML file outputs. Enjoy!
Here is the source code and awk scripts for those interested. Please give me credit and send me a lot of money if you get rich and famous using any ideas from the source :-)
- Here is the entire source code zip pack. Alternatively select individual items below.
- My awk scripts used to generate canonical input from the originals:
- The HTML output wrapper
- The C source
There are 32 output files made up of 16 text files and 16 HTML files. These are all linked in the table below.
Canonical Representation Of Factorisations
- Factorisations are given from smallest to largest factor, with a period '.' separating factors.
- Multiplicity of factors is indicated with the carat '^' in ascii tradition for the text version of the tables but not the HTML version.
- The backslash '\' is used to indicate continutation of a line, the decimal digit representation of the number does not stop but continues on the next line as if no break had occured. This can sometimes make for bad breaks, but such is life.
Notation Used In The Tables
The following colour coding and hyperlinking conventions are adopted:
- Composite exponents are in black. C±(b,n) is composite in this case.
- Prime exponents are coloured orange. C±(b,n) is usually composite in this case too.
- A prime C±(b,n) is coloured green - this is a rare jewel and ignoring n=1 cases can only occur in C−(2,n) with n prime (Mersenne primes) and C+(b,n) with b even and n a power of 2 (Generalised Fermat primes).
- Factors in an expression coloured red are unfactored. They are known to be composite but there are currently no known factors.
- Hyperlinked numbers occur in previous exponents in the same or related table.
- #Fac is the number of (non distinct) prime factors in an expression.
- A dashed #Fac means that more prime factors exist but they are unknown due to an unfactored composite in the expression.
C−(b,n) C−(2,n) C−(3,n) C−(5,n) C−(6,n) C−(7,n) C−(10,n) C−(11,n) C−(12,n) C+(b,n) C+(2,n) C+(3,n) C+(5,n) C+(6,n) C+(7,n) C+(10,n) C+(11,n) C+(12,n)
You can download the entire factor packs to your local machine to save your internet bandwidth. These tables are fairly large (up to 1MB in size).
Cunningham Factors Text Output Pack (0.9 MB) Cunningham Factors HTML Output Pack (1.4 MB)
Mostlate breaking information can be obtained from the sites listed below. They should be your first stop if you want the latest, up to date factorisation status.
- ECCM Page At GIMPS
- ECCP Page At GIMPS
- Paul Leyland's Cunningham Updates (link no longer available).
- Cunningham Site - New Factors
The C−(b,n) numbers are composite when n is composite. This is the result of an algebraic factorisation that many will recognise as the geometric series formula they learned in high school. More formally, if m,n are postive integers and m divides n, then bm - 1 divides bn - 1. The proof of this amounts to observing that x -1 divides xa - 1 for natural numbers x and a because
xa - 1 = (x - 1)(1 + x + x2 + ... + xa-1)
Thus if m divides n then n=m*a for some integer a>=2. The result follows by setting x=bm in the above identity.
A corollory to the above result is that because x - 1 divides xa - 1, a necessary condition for xa - 1 to be prime is that x=2 and a is prime.
If you have trouble understanding the above result, try multiplying out the terms on the right hand side and notice that all but the largest and smallest terms cancel out in pairs. Trying doing an induction proof if you are really skeptical.
This is also a result of an algebraic factorisation that many will recognise from high school. First observe that if b is odd then C+(b,n) is an even number (odd powers are odd and odd plus odd is even). Thus it is clear that if b is odd then 2 divides C+(b,n).
Next, notice that if n has an odd factor a then n=m.a for some integer m and
C+(b,n) = bn + 1 = (bm)a + 1
Now use a variation of (GS) above obtained by replacing x by x/y and a by n and multiplying by through by ya we have the alternate identity
xa − ya = (x − y)(xa−1 + xa−2.y + xa−3.y2 + ... + x.ya−2 + ya−1).
Substituting in y=−1 gives
xa − (−1)a = (x + 1)(xa−1 − xa−2 + xa−3 + ... + (−1)a−2.x + (−1)a−1)
which yields in the case of odd a
xa + 1 = (x + 1)(xa−1 − xa−2 + xa−3 + ... + −x + 1).
Finally comparing the first and last equations above and setting x=bm yields the result that bm + 1 divides C+(b,n) when n has an odd factor a because
ba.m + 1 = (bm + 1)(bm(a−1) − bm(a−2) + bm(a−3) + ... − bm + 1).
A corollory to the above result is that if b>1 and C+(b,n) is prime, then a necessary condition is that b is even and n=2m for some integer m>=0. Not surprisingly, numbers of this form have been given their own name - The Generalised Fermat Numbers and are denoted by GF(n,b) = bN + 1 where N = 2n. When GF(n,b) is prime it is referred to as a Generalised Fermat Prime.
As a final remark, the polynomial xN + 1 is the 2n+1th cyclotomic polynomial and is thus irreducible over the rationals. This means it cannot be written as the product of two positive degree polynomials with rational coefficients. In other words, there is no further algebraic factorisation possible. This does NOT mean that further integer factorisation is not possible though when x is set to b.
Another algebraic factorisation that is particularly useful when n is even, is the difference of two squares. Simply stated, a2 − b2 = (a − b)(a + b). If n=2m say, then this formula gives:
C−(b,n) = C−(b,2m) = b2m − 1 = (bm)2 − 12 = (bm − 1)(bm + 1) = C−(b,m).C+(b,m).
In other words C−(b,n) can be factored into a product of a smaller Cunningham numbers (one from the same table and one from a related table).
Consider the following identity:
22h + 1 = L.M where L = 2h − 2k + 1, M = 2h + 2k + 1, h = 2.k − 1.
This factorisation was discovered by Aurifeuille for one value and the general form subsequently discovered by Lucas. There are other Aurifeuillian factorisations, I list some of them below. There is much to be learned in this area. You can easily establish the above identity by multiplying out the right hand side and simplifying. A deeper explanation however will require a study of both Cyclotomic and Aurifeuillian polynomials. It turns out that they can be explained well in terms of roots of unity − you will have to start up your search engine to find more details.
33h + 1 = (3h + 1).L.M where L = 3h − 3k + 1, M = 3h + 3k + 1, h = 2.k − 1.
55h − 1 = (5h − 1).L.M where L = T2 − T.5k + 5h, M = T2 + T.5k + 5h, T = 5h + 1, h = 2.k − 1.
66h + 1 = (62h + 1).L.M where L = T2 − T.6k + 6h, M = T2 + T.6k + 6h, T = 6h + 1, h = 2.k − 1.
77h + 1 = (7h + 1).L.M where L = T3 − B, M = T3 + B, T = 7h + 1, B = 7k(T2 − 7h), h = 2.k − 1.
1010h + 1 = (102h + 1).L.M where L = A − B, M = A + B, A = 104h + 5.103h + 7.102h + 5.10h + 1, B = 10k(103h + 2.102h + 2.10h + 1), h = 2.k − 1.
1111h + 1 = (11h + 1).L.M where L = A − B, M = A + B, A = 115h + 5.114h − 113h − 112h + 5.11h + 1, B = 11k(114h + 113h − 112h + 11h + 1), h = 2.k − 1.
123h + 1 = (12h + 1).L.M where L = 12h − 2h.3k + 1, M = 12h + 2h.3k + 1, h = 2.k − 1.