The Cunningham Project

Back

In 1925, Lt.-Col. Allan J. C. Cunningham and H. J. Woodall published a small

volume of tables [11] of factorizations of bn _ 1 for the bases b = 2, 3, 5, 6, 7, 10,

11, 12 to various high powers n. These tables collected from scattered sources the

known prime factors for the bases 2 and 10 and also presented the authors' results

of thirty years' work with these and the other bases. (See [11, pp. xii, xviii] and

[55] for a general survey of factor tables.)

For decades these useful tables served as a basic reference on factors of these

numbers. The tables were not only a summary of what was known, but a disclosure

of what was not. Furthermore, by leaving blanks in the tables where new factors

could be entered, by putting question marks on numbers of unknown character,

and by giving credit to those who had discovered notable prime factors in the past,

the authors stimulated work on the remaining composite numbers in the tables.

In the Introduction to the tables, a somewhat unsatisfactory account of the

multiplicative structure of bn _ 1 was given in a rather _nicky notation and terminology.

Many useful examples were given to illustrate how numbers of the di_erent

forms factor. However, much remained unsaid as to just how the numbers factor

algebraically and how the various algebraic factors divide one another.

This is particularly true in the section on Aurifeuillian factorization, where

there is no mention of the form of the primitive part in such factorizations. As

is clear from the parenthetic remark at the bottom of page vi, the authors knew

neither this form nor the rule that determines which L or M will divide another L

or M [36, p. 181]. All in all, though, this pleasant and important little book|a

labor of love|was and is much valued by those who are fortunate enough to own

a copy.

In the _fty years following 1925, some copies of these tables became so _lled

with inserted factors and other information that the present volume, which we consider

to be an extension and an updating of the earlier tables, comes none too soon.

Many new prime factors have been discovered in the last thirty years through the

use of computers and by new methods of factoring and primality testing. Evidence

of this abundance can be seen, for example, in the fact that all the numbers in the

*The text of this Introduction is essentially that used in the _rst edition. A few typographical

errors were corrected and the old status report was deleted. The new text for the second edition

appears in Section IV. The new text for the third edition appears in Section V.

xlv

III A THE CUNNINGHAM-WOODALL TABLES xlvi

Cunningham-Woodall base three tables (up to n = 111) are completely factored in

the present work, and that it is no longer feasible to keep track of the discoverers

of all the new prime factors.

In a way, it is sad that rapid and accurate automatic computers have spoiled

the hand calculator's pleasure and feeling of accomplishment in factoring what was

an immense number. Indeed, many of the factors in these tables were monuments in

their day to this kind of achievement. But transcending the limits of human power

by machines can bring with it, all the same, a new sense of power in achievement

and also a freedom from drudgery which may well stimulate the devising of new

methods and the setting of new goals when the old goals are reached. And certainly,

there is still a real feeling of accomplishment in breaking apart some huge number

which has withstood assaults for decades, especially when in doing so one has had

to devise and carefully carry out some new computational scheme. The current

invasion of small electronic computers into homes and o_ces may well lead to

renewed interest in attacking the large composite numbers still remaining in these

tables.

For many years we have referred to the ongoing work on these tables as \The

Cunningham Project". As new factors have been found or primality tests have

been completed, the accumulation of information has prompted a continual reorganization

of the data into forms better suited to updating. The new data, which

at _rst were written in the Cunningham-Woodall tables, were later transferred to

boxes of Hollerith cards, making the modi_cation and listing of the tables much

simpler. In 1968 BT (authors' initials will be used throughout this work), using an

IBM 360/67 at the Thomas J. Watson IBM Research Laboratories, systematically

found all factors < 108 of most of the entries in the present tables (except for base

2), of which many were new. He also discovered the compositeness or probableprimality

of all the cofactors using Fermat's congruence, at the suggestion of JLS.

This information was incorporated manually into the _les of Hollerith cards. In

1970, Mike Morrison and JB subjected the resulting tables to a computer checking

scan on the IBM 360/91 at UCLA. Several errors were discovered among the data

manually accumulated over the years. In later years, the data were placed in a

data set (disk _le) on the computer system at Northern Illinois University, DeKalb,

along with all the primality testing information that had accumulated for years in

an impressive stack of computer printout.

With all the information in a data set (and the large stack of printout happily

thrown away), new formats were devised which provided for a simple presentation

of prime and algebraic factors in the tables in which a prime factor is listed as such

only once at its _rst appearance. Some of the remaining problems in the tables were

identi_ed and listed, and the factoring and primality testing programs available at

DeKalb were set to work in an attempt to solve these problems.

Substantial progress has been made over the last several years, and the range

of n has been extended in each table, although we have used only the original bases

of the Cunningham-Woodall tables.

The present tables are now at the limits of what can be done by factoring

through 50 digits using the method in [75], although more progress will no doubt

be made when the two excellent factoring methods of J. M. Pollard [80, 81] have

been used more. We have listed in Appendix C the remaining composite cofactors

with 64 or fewer digits as an aid or a challenge to venturesome readers. (See IV

for the progress made between the _rst and second editions of this book.)

xlvii III B 1 DEVELOPMENTS IN TECHNOLOGY

When the tables were essentially ready for distribution, SSW wrote and ran

a checking program which tested the factorizations in the di_erent tables to see

if: (1) a listed factor actually divided the respective number; (2) all factors were

present in complete factorizations; (3) all factors listed were probable primes base

13; (4) the line numbers listed in parentheses were complete and correct. Minor

checking was also done to see if the lengths of cofactors were correct and if periods

and parentheses were in the right places. Finally, the cofactors themselves were

again checked as probable primes base 13 and were stored in the proper appendices

along with their labels and lengths.

Навигация