Reference / Paper · 1994
Factoring Integers Before Computers (Proc. Symp. Appl. Math. 48, 481–531)
The standard history of mechanical factoring: Carissan, Gérardin, Kraitchik and the Lehmers' sieves.
Reference / Paper · 1994
The standard history of mechanical factoring: Carissan, Gérardin, Kraitchik and the Lehmers' sieves.
480 CARL POMERANCE 24. C. Pomerance and J. W. Smith, Reduction of huge, sparse matrices over a finite field via created catastrophes, Experimental Math. 1 (1992), 90-94. 25. O. Schirokauer, On pro-finite groups and on discrete logarithms, Ph.D. thesis, University of California, Berkeley, May 1992. 26. D.. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54-62. Department of Mathematics University of Georgia Athens, Georgia 30602 U.S.A. e-mail: [email protected] Proceedings of Symposia in Applied Mathematics Volume 48, 1994 Factoring Integers Before Computers H. C. WILLIAMS AND J. O. SHALLIT Dedicated to the memory of our friend, D. H. Lehmer (1905-1991) ABSTRACT. We examine some aspects of the history of computational num- ber theory, with emphasis on the problems of integer factorization and primality testing. 1. Introduction We revel in the details of history because they are the source of our being. Stephen Jay Gould During the last twenty years, the field of computational number theory has achieved the status of a discipline in its own right. This development is due, in large part, to the invention of cryptosystems (methods for encoding and decod- ing messages) whose security is based on the presumed computational difficulty of certain number-theoretic problems such as integer factorization. Also quite in- fluential was the development of the theory of computational complexity, which enabled the comparison of different algorithms to be placed on a firmer mathe- matical footing. Because of the influence of these two areas, one may legitimately ask whether computational number theory is properly a part of mathematics or computer science. But, of course, the most profound influence upon the establishment of com- putational number theory is the development of the computer. From the very beginning of computer technology (and, as we will see, even before then), num- ber theorists were using whatever “hardware” was available to aid them in their research. 1991 Mathematics Subject Classification. Primary 11Y05; Secondary 11Y11, 11A51, 11Y16, 01A55, 01A60. Key words and phrases. Primality testing; factoring. The research of both authors is supported in part by grants from NSERC of Canada. This paper is in final form, and no version of it will be submitted for publication elsewhere. 1994 American Mathematical Society 0160-7634/94 $1.00 + $.25 per page 481 1 1 ' t 482 H. C. WILLIAMS AND J. O. SHALLIT Computational number theory, unlike many other areas of mathematics, is properly a science: experimental method is a significant component in practice. Those who develop number-theoretic algorithms are often concerned with their eventual implementation, and a great deal can be learned from such experimen- tation. The release from the immense drudgery of hand calculation afforded by elec- tronic computers leads to a much more thorough development and testing of algorithms, and gives us new insight into the theorems on which those algo- rithms are based. Furthermore, it becomes possible to use algorithms that are extremely complicated: many powerful modern methods would be completely unusable if only hand computation were available. Given this, why should we even consider computational number theory before the age of electronic computers? The answer is that the subject was studied for centuries before computers were available, and it is in this work that the modern subject claims its origins. It is important to understand and appreciate the ingenuity and tireless energy of the pioneers of our discipline. It is easy to be condescending toward these people; after all, they did not express their ideas using modern terms such as “polynomial time” or “succinct certificate” that we casually use today. Although they had not formulated such language, they often understood the ideas implicitly.! Since they did their calculations by hand or with the aid of simple mechanical tools, they had to be concerned with efficiency and accuracy. ; Why did the early workers in computational number theory not use machines? The answer is that they did: not only did they make use of whatever calculating device was available at the time, on occasion they even developed new machines, as we will see later. One great difficulty that frequently plagued these researchers was that the technology of the day was simply not equal to the demands of the mechanisms they envisaged. For example, according to some historians, Babbage’s failures with the differential engine were due in part to the inadequacy of the British machine-tool industry at the time (but for a different view, see [176]): A sieving device described by Lawrence in 1896 was only constructed successfully by Carissan in 1919. Furthermore, it was not until 1932 that Lehmer was able to make a sieve mechanism run at a fairly rapid rate without human intervention. Another problem, easy to appreciate by researchers of today, was the difficulty in obtaining research funding for these projects. . We do not intend in this paper to provide anything like a complete history of the development of computational number theory. For our purposes, it will suffice to illustrate our points by concentrating’on one particular problem which is still of great interest today: the integer factoring problem. Indeed, the only “proof” that this problem is intractible (a very important issue in modern cryp- tography) is based on its history. More precisely, we will study the computational 1In making this observation, we hope, of course, to avoid the fallacy of interpreting historical events solely in the light of modern understanding. FACTORING INTEGERS BEFORE COMPUTERS 483 history of both factoring and primality testing. These two problems really do belong together, because if we wish to obtain the complete factorization of an integer N as a product of prime powers, we must be able to show that the primes involved in this representation are indeed primes. Also, as we will see below, a partial factorization of numbers like N — 1 and N +1 proves useful if one wants to prove that N is prime. These problems have a very long history, but, with the exception of the inven- tion of the Eratosthenian sieve, nothing truly significant was done until the time of Fermat. From then on, progress has been steady (if not always spectacular) up to the present day. We emphasize here that early researchers in computational number theory were often uninterested in general methods for factorization or primality testing; rather, particular classes of numbers (such as 27 + 1 and 10" + 1) served as stimuli for their efforts. The reader is no doubt familiar with the stories of Mersenne’s discussion of the primality of 2” — 1, and Fermat’s incorrect belief that all numbers of the form 2?” +1 are prime. In 1856, Reuschle [159] published (among other items) a table of factors of 2" — 1 and 10" — 1 for n < 42, and in 1869, Landry [63] published a table of factors of 2-1 for n < 64. The “holes” in these and other tables provided a source of challenges in factoring and primality testing that occupied the energies of many workers over several decades, as do the holes in the Cunningham Table [13] even today. Our main focus in this paper is on the computational history of factoring and primality testing from 1750 to about 1950 (although we discuss modern work in §14). (For citations before 1750, the reader may consult Volume 1 of Dickson’s History of the Theory of Numbers [20].) Nevertheless, it may be of some interest for comparison’s sake to mention what can currently be done. The largest prime currently known is 2756839 — 1, a number of 227832 decimal digits. This was discovered by Slowinski and Gage on 19 February 1992; see Ewing [23]. One of the largest integers ever proved prime by a general method? is (2599 + 1)/3, a number with 1065 decimal digits; see Atkin and Morain [3] and Bosma and van der Hulst [10]. D. Bernstein and A. K. Lenstra announced the factorization of 2523 _ 1, a 158-digit number, on 29 October 1992; they used the lattice sieve, a version of the number-field sieve. The largest integer ever factored by a general method is a 116-digit divisor of 10/47 +1, by A. K. Lenstra, M. Manasse, and the assistance of many others; see [98]. For further information on this subject, we refer the reader to the papers of Williams [186], Silverman [172], and the books of Riesel [161], Bressoud [11], and the Cunningham project book of Brillhart et al. [13]. 2By a general method we understand an algorithm that does not depend on any special properties of its input. For example, a primality testing algorithm that applies only to numbers of the form 2” — 1 would not be a general method. 484 H. C. WILLIAMS AND J. O. SHALLIT 2. Primality testing We begin our discussion of the history of computational number theory with the problem of testing a positive integer for primality. From a modern point of view, the definition of the term “primality test” is not universally agreed upon. (Indeed, the authors of this paper are not in complete agreement!) In general usage, a test can mean a “procedure for determining the presence or absence of some property”; consider, for example, “syphilis test”. As the term is generally understood, a test may not be accurate with 100% confidence. It is also possible for a test to return the result “inconclusive”. This intuitive usage of the term “test” is what is generally meant by most complexity theorists. By a “primality test”, most complexity theorists under- stand any randomized algorithm® that recognizes either the set of prime numbers or the set of composite numbers. More precisely, any Atlantic City algorithm is regarded as satisfactory; here, Atlantic City refers to an algorithm with the property that the output may be incorrect, but the probability of error is no more than 1/2 ~ ¢, for some fixed positive constant ¢. It is important to note that the probability of error does not depend on the input N; rather it is com- puted by considering all possible sequences of coin flips used by the algorithm. If a set is accepted by an Atlantic City algorithm running in polynomial time, then we say that the set is in the complexity class BPP (bounded away from zero probabilistic polynomial time). It is known that the set of prime numbers are in this class; thus, complexity theorists and cryptographers are generally happy with the algorithms of Solovay-Strassen [173] and Miller-Rabin [156]. However, many number theorists find this rather general definition unsatis- factory, since Atlantic City primality tests do not, in general, provide a proof that a prime number really is prime - only good evidence that this is the case. (However, the Solovay-Strassen and Miller-Rabin algorithms actually have one- sided error, and hence if they reply “composite” on input N, then a proof that N is composite is provided by the details of the computation.) In contrast, most number theorists do not object on philosophical grounds to the so-called Las Vegas tests: these use a source of random numbers, but their output does pro- vide a proof that the number in question is either prime or composite. Only the running time, not the conclusion, of a Las Vegas algorithm is probabilistic. If a set is accepted by a Las Vegas algorithm running in expected polynomial time, then we say that the set is in the complexity class ZPP (zero error probabilistic polynomial time). 7 ° As most of the early workers tended to regard a primality test as being a technique which would yield a rigorous proof of primality, we will adopt for use throughout this paper the following more narrow definition of “primality test”: DEFINITION 2.1. A primality test on a given integer N is the computational 3A randomized algorithm is one that has access to a sequence of random, unbiased flips of a fair coin, FACTORING INTEGERS BEFORE COMPUTERS 485 verification of the hypothesis of a theorem whose conclusion is that N is prime. Some have also called such a test a “primality proof’. Many such tests can be described. For example, consider Wilson’s theorem (which was probably known to Leibniz; see Vacca [185] and Mahnke [127]): N > 1is a prime if and only if N divides (N ~ 1)!+1. However, this test seems to be computationally impractical, since there is no known way to compute (N — 1)!+1 (mod N) in any reasonable length of time for large N. (Note that Wilson’s Theorem actually gives a necessary and sufficient test for primality, something not explicitly required by our definition.) Having described what we mean by a primality test, we now give four features that are desirable: the test should be efficient, the test should be universally applicable, the test should be robust, and the test should produce an efficiently verifiable certificate of primality. The term “efficient” is, of course rather vague and subject to interpretation, but most would agree that the obvious implementation of Wilson’s theorem is not efficient. Today we might say that an algorithm is efficient if it runs in polynomial time, that is, if its running time is bounded by a polynomial in log N, where N is the input. This definition has its problems in real life, however, since the polynomial referred to may have high degree or very large coefficients. For example, although it is a great theoretical advance, the Las Vegas primality test of Adleman and Huang [1] is probably not useful in practice for precisely these reasons. The second feature, universal applicability, means that the test should work for all prime numbers. This is a desirable goal, but one that not all otherwise useful tests satisfy. As we will see below, many of the early practical primality tests only worked for numbers of special forms: Lucas’ test for numbers of the form 2? — 1, for example. The third desirable feature of a primality test is robustness. Robustness is a vague notion which is difficult to express precisely; we use it to mean that errors that take place during the course of the computation will be detectable. Here is an example: suppose we are trying to determine if a number a is a quadratic residue modulo some given odd prime p. By Euler’s criterion, it suffices to compute a'?—))/2 (mod p). The result, if computed correctly, will be +1 or —1, according to whether a is a residue of nonresidue. Nearly every mistake made in this computation will be detectable, since most will result in an answer which is neither +1 nor —1. . Robustness was especially important in the days before computers, when hand computation was very error-prone, and checking a computation was not simply a matter of running a program again on another machine. Lucas’ necessary and sufficient test for primality of numbers of the form 2? — 1 depends on obtaining the result 0 after a long series of hand calculations involving numbers with p bits. If the result is 0, then one may be reasonably confident that it is correct, and hence the number in question is prime, since the probability of obtaining 0 486 H. C. WILLIAMS AND J. O. SHALLIT after a random series of multiplications and additions of numbers this large is quite small. On the other hand, if the result is not 0, the theory implies that the number in question is composite. But since almost any error introduced into the computation would also give a nonzero result, one’s confidence in this result is necessarily smaller. The last criterion, that of producing an easily verifiable certificate of primality, was explicitly pointed out for the first time by Pratt in 1975 [150]. He showed that, for any given prime p, it is possible to obtain a “succinct certificate” that proves p prime and which can be verified in polynomial time. It is, of course, quite conceivable that actually finding such a certificate may require more than polynomial time. Note that we have not discussed what may happen if the input to a primality test is composite. There are several possibilities: the algorithm may diverge (run forever); the algorithm may reply that the test is inconclusive; or the algorithm may provide a proof that the input is indeed composite. While this behaviour was a legitimate concern in the past, today a proof of compositeness may be given in polynomial expected time using the strong pseudoprime test (as in Miller-Rabin). Having discussed some abstract principles, we now move on to the history of primality testing. In 1588, Cataldi proved that Ny = 524287 = 2!9 —1 is a prime by trial division by all the primes less than the square root of Nj. (The method of trial division was known to Fibonacci in 1202.) Until 1772, this seems to have been the largest prime known. At that time, Euler proved that Nz = 2147483647 = 23! — 1 is a prime. He did this by improving upon the algorithm used by Cataldi. Euler was aware that if any prime q is a divisor of 2? — 1, where p is an odd prime, then g = 1 (mod 2p), a result known to Fermat. He also realized that since 2N2 = (216)2 — 2; then 2 must be a quadratic residue of g; hence g = +1 (mod 8). By combining these observations, Euler could assert that if g is a prime divisor of No, then g = 248k + 1 or gq = 248k + 63 for some integer k > 0. If q < Ne, then there are only at most 186 values of k to check. Thus, after performing at most 372 trial divisions (fewer if one eliminates composite trial values of q), Euler was able to show that Nz is a prime. Thus, Euler’s test was more efficient than Cataldi’s. In 1859, F. Landry [61], who at that time believed that 23! — 1 was still the largest known prime’, attempted to give a shorter proof of its primality than Euler’s. By using a number of clever tricks he was able to do this; in fact, by 1867 he was able to claim [62] that he had so reduced the calculations necessary to effect the verification of the primality of N2 that they would fit on a single slip of paper. Furthermore, in this same paper Landry goes on to state that he had proved the primality of the thirteen-digit divisor 1133836730401 of 27° +1. 4In fact, according to Reuschle [159, p. 3], Looff had proved in 1851 that 999999000001, the 12-digit factor of 10'8 + 1, is prime. FACTORING INTEGERS BEFORE COMPUTERS 487 What he said next we quote here, in translation from the French: At this point we are, if not uneasy, then at least somewhat embarrassed. Indeed, when one has succeeded in factoring a number, and has given its factors, this can be verified immediately. But it is a different matter when the methods used fail to discover any fac- tor, and one then asserts that the number is prime. How could one then transmit to another such a totally personal conviction? Who would be convinced, without having redone all the calcu- lations, and without having understood the principles on which those calculations were based? We understand well that our claim is valid only as an assertion, worthwhile until someone proves the contrary, or until we make known our methods and enable others to apply them. Today, we would say that Landry was struggling with the difficulty of pro- viding a succinct certificate. Landry clearly anticipated the basic idea of what would become famous a hundred years later in computational complexity theory: the class NP. Even today, providing such a certificate is a difficult problem, and those who have been involved in primality testing can easily understand and appreciate Landry’s concern. In 1869, Landry [63] went on to state that he had proved that the 14-digit number (25% + 1)/(3- 107) is prime. This was the largest prime known until 1876, when Lucas made his breakthrough. Incidentally, Landry did not describe in (62, 63] how he had carried out his impressive factorizations. It was not until 1880, when he wrote a letter [64] to Charles Henry, that he revealed his method. Landry’s technique had been known to Fermat and will be described later. (It was this convergence of techniques that particularly struck Landry and caused him to write his letter.) After Landry’s work in 1869, only the following four numbers of the form 2” + 1 (n < 64) remained unfactored: 2° — 1, 281 _ 1,281 4 1, 964 47, By 1878, Landry (according to Lucas [114, pp. 239-240]) had factored 2°° — 1; we will discuss the investigation of the others later. It is interesting to note in passing that Landry suspected that 26! — 1, (2°! + 1)/3, and 264 + 1 were all primes, but he never seems to have said that he had proved the primality of any of them. Indeed, in [63] he stated that these had resisted his efforts, and in 1880 he said {64] that the first two still remain to be investigated (the third is composite). 2.1. Babbage. Charles Babbage, the English pioneer of the modern com- puter, was one of the first to apply computational ideas to number theory. Legendre and Euler had both noticed that the polynomials x? + « + 41 had the unusual property of generating nothing but primes for small values of x. The 488 H. C. WILLIAMS AND J. O. SHALLIT relationship between this curiosity and the class number of Q(./—163) was not explained until 1912 by Frobenius and Rabinovitch. Babbage knew about these polynomials, and one of the first tasks he set his Difference Engine to was the computation of values of x? +2+41. In June 1822, he wrote: With this machine I have constructed ... a table from the sin- gular formula x? + x + 41, which comprises amongst its terms so many prime numbers. His machine could only display results, and not print them. Babbage employed a friend to write down the results. In a letter to Sir Humphrey Davy the next month, Babbage discussed the speed of his machine: [The Difference Engine] proceeded to make a table from the formula 2*+2+41. In the earlier numbers my friend, in writing quickly, rather more than kept pace with the engine; but as soon as four figures were required, the machine was at least equal in speed to the writer. The letter also mentioned a possibility for a future machine (perhaps the Analytical Engine): ‘T have also certain principles by which, if it should be desirable, a table of prime numbers might be made, extending from 0 to ten millions. See Babbage’s collected letters and papers [4] for more details. 3. Lucas’ discovery In order to discuss the work of Edouard Lucas, it is first necessary to introduce the functions that today carry his name. The Lucas functions U,, and V,, (or Un (P,Q) and V,,(P, Q)) are defined by where a, 3 are the zeros of the polynomial 22 — Px +Q, and P,Q are coprime integers. These functions did not originate with Lucas; they (or functions very similar to them) had been studied by Euler, Lagrange, Legendre, and Gauss. Several combinatorial and number-theoretic properties of the function U,, had been dis- covered by Siebeck [171] almost thirty years previous to Lucas’ work. Also, Genocchi [33] had used properties of functions very similar to U, and V,, in order to demonstrate the infinitude of primes of the forms az +1 and az ~ 1, for any given a. Nevertheless, in our opinion the functions are properly called the Lucas functions because of Lucas’ singular contribution to their study, only a part of which we will discuss here. In early January of 1876, it appears that Lucas [102] had considered the functions U,, and V, as we see them above, but he was mainly interested in the FACTORING INTEGERS BEFORE COMPUTERS 489 particular case of U,(P,Q) where P = 1 and Q = —1. Today, these numbers are called Fibonacci numbers, but at the time it was common to call the sequence (3.1) 0,1, 1,2, 3, 5,8, 13, 21, 34,... the series of Lamé. That was because Lamé [60] in 1844 had used these numbers to investigate the number of steps performed by the Euclidean algorithm to compute the greatest common divisor of two numbers. Lamé had shown that the worst case of the Euclidean algorithm occurred when the inputs were successive Fibonacci numbers, a fact that had been given without proof by Léger [69] in 1837. This is one of the earliest results in the analysis of algorithms. Lamé further showed that the number of division steps in the Euclidean algorithm was always bounded by five times the number of decimal digits in the smaller of the two inputs. It was Lucas, however (see [103] and [112]), who discovered that these numbers had been known to Fibonacci six centuries earlier, and in Lucas’ next paper [103] dated May of 1876, he calls (3.1) the Fibonacci series. There are several results mentioned in [102], all given without proof, but the most striking of these are results such as the following. THEOREM 3.1. If N = +3 (mod 10), N|Un41, and NJUq for all divisors d of N +1 [withd << N+], then N is a prime. The reason for the importance of this theorem will be fully discussed later. Lucas pointed out that it permits one to know that a number is prime or compos- ite without the need of a table of primes, i.e., without employing trial division. Notice that this is somewhat similar in spirit to Wilson’s theorem in that to show that N is a prime it is necessary to show that it divides a certain number. However, Lucas was the first individual to devise an efficient test for primality or compositeness, which did not necessarily have to reveal the factors, if any, of the number being tested. He then goes on to say: It is with the aid of this theorem that I think that I have shown that the number N = 2!?7 — 1 is a prime. This N = 170141183460469231731687303715884105727 is a number of 39 dig- its, far greater than the largest prime known at the time. (Lucas at this time was unaware of the work of Looff and Landry and thought that 2°! — 1 was the largest known prime.) Lucas had clearly made a most remarkable discovery, and when we think about his statement today, there are at least four important questions that we are led to ask: (i) How did Lucas discover this test? (ii) Why did he test 2127 — 1, and not some other number? (iii) How did he test 212” — 1? (iv) Why was he unsure of the result? We will attempt to answer the first two of these questions in this section, leaving for later sections the answers to the others. Previous to his paper [102], 490 H. C. WILLIAMS AND J. O. SHALLIT Lucas had written only one other paper [101] on factoring. In this paper he at- tempts to factor various numbers of the form a” +1 by determining the possible linear forms of the prime divisors (as did Euler) and then performing trial divi- sions by taking logarithms of the numbers involved and subtracting. This work, which appeared in November of 1875, seems much less sophisticated than the work of the following January. What happened? In [118, p. 14] Lucas himself provides us with the answer. In commenting on [102] he says: This note is the point of departure for new investigations by the author in the theory of prime numbers. After having decom- posed by means of a table of prime divisors the early terms [of the Fibonacci numbers], the observations of the forms of these divisors led the author to the demonstration of a certain num- ber of theorems which allowed him to develop some new and general considerations concerning the theory of prime numbers. One finds here for the first time an indication of a new method for finding prime numbers, which is independent of a previously constructed table of prime numbers. As to why Lucas selected 2127 —1 to test, we can only speculate. Probably he wanted to find a prime of the form M, = 2" —1; after all, Euler himself had been interested in such primes and Euclid had shown that 2"~!M,, is a perfect number when M,, is a prime. Also, it is easy to find all of the divisors of M, +1 = 2"; thus, the theorem of Lucas quoted earlier is easy to apply (see §4 below). Lucas knew that any prime value of M,, would require that n be prime and he also knew all the primes of the form M,, that had been identified by 1876: 2? — 1,29 ~1,2° — 1,27 ~ 1,238 — 4,917 1,919 4 931 4, Notice that some of these values of n (i.e, 3, 7, 31) are also of the form My. The next possible prime value for such an n is 127 and Mj27 = —3 (mod 10); thus, his theorem could be used. We don’t really know that this was how Lucas was thinking, but in a later letter [111] he speculates on the existence of a sequence of primes of the form 2” — 1,271 ~ 1,92 — 1,..., where n; = 2” ~—1, ng = 2"! — 1, etc.; thus, it’s quite likely that he was thinking along the lines of our speculation. According to [118], Lucas wrote a thesis for presentation to the Faculty of Science at Paris. This thesis, dated September 24, 1877, was a development of the paper [102] and could perhaps cast some. ‘further light on these problems. Unfortunately, all attempts by the authors to locate a copy of it have so far failed. 4. Implementation of Lucas’ test In order to discuss how Lucas actually used his theorem to test Mjo7, we provide the following simple identities satisfied by U,, and V,: FACTORING INTEGERS BEFORE COMPUTERS 491 On examining these identities and referring back to Lucas’ theorem, it is easy to see that if N = 2"—1 and N|Un41 but N{Uq for any proper divisor d of N +1, then N|Viviiy/2. Thus, if we define S, = V2.(1,—1), then 5, = S2_, - 2 for k > 2. We have the following test: If M, = +3 (mod 10), then M,, is a prime if M,|S,-1, where 5, = 3 and S, = S2_, —2 (mod M,) (k = 2,3,...,.n —1). Notice that this test for primality certainly possesses the features of efficiency and robustness discussed in §2. As he mentions in [112], this is the form of the test that Lucas used. By December of 1876 he [107] has modified this result as follows: THEOREM 4.1. Let p = 24+3 — 1, where the exponent is a prime. If one forms the sequence 3, 7,47, 2207,... with ry) = 3 and Ta41 = r2 —2, then p is a prime when the least value of k such that plr;, is 4m+2. The number is composite if none of the first 4m + 2 values of Tn is divisible by p. Finally, if a denotes the first value of k such that pire, then. the [prime] divisors of p have the form 2°t +1 combined with those forms which can divide x? — 2y?. So we know what sort of test Lucas used, but how did he actually perform -the arithmetic? Remember Mj27 is a number of 39 digits; the kind of arithmetic needed here would involve numbers larger than any used previously. In several papers Lucas [103, 106, 108, 114] alludes to the use of binary arithmetic for doing this, but he does not really describe how he actually did it. Finally, in [112, p. 152 ff] he is more explicit. The solution to this problem is very characteristic of him; he made the performance of this tedious arithmetic into something like a game. He said he used a 127 x 127 chessboard to effect the computations. To illustrate his idea he used a simple example which we will discuss here. Consider (instead of Miz7) M7 = 27-1 = 127. We have S; = 3, S: = 7, S3 = 47, Sy = 472 —2 = 48 (mod 127), Ss = 482 — 2 = 16 (mod 127), Se = 162 — 2 = 0 (mod 127); hence, we have a proof of the primality of 127. Lucas notes that if M, = 2” — 1, then (4.1) grntm = 2™ (mod M,,). The main operation of testing involves squaring, subtracting 2, and reduction modulo M,,. If we try to perform this on $3 to obtain S4 (using M7) we first consider the binary representation of S3 which is 101111. We can then begin to 492 H. C. WILLIAMS AND J. O. SHALLIT compute its square by simply multiplying as usual 10314141 10321311421 10311141 10321141 103113141 101%14d1421 000000 1o01i1iti1é4z1 However, because we only need to find the answer modulo 27 — 1, we can use (4.1) to put the information between the horizontal lines into a neat 7 x 7 square because each row wraps around cyclically. 7/64}514/3)/2/1 O;1)/O;1;1f1i}i 1;/O/1/1}1;1]o O;1}1}/ijrypola 1/1}1/1/o0;1]0 L1}1{/1}/0/1)/0/1 0|/0;0/0/0!0/;0 1}/1/0/1/0/}4]1 In order to avoid a lot of writing, Lucas suggests the use of a 7 x 7 chessboard with pawns in squares representing the positions of the ones and empty squares representing the positions of the zeros. Once we have this array of pawns on our chessboard we make use of two rules: (i) Take (when possible but only once) a pawn away from column 2. This corresponds to the subtraction of 2 from the square. If a pawn never appears in column 2, then 2 must be subtracted from the final answer. (ii) For each pair of pawns in any column remove one from the board and move the other into the column to the left. Remember that the column to the left of the left-most column (column 7 here) is column 1 because of (4.1). Continue performing these operations until the only pawns_remaining are in the first row. In our case we get the first row to be 716/5/4;3]/2/1 which represents 0 1 1000 0 or 48 in decimal. Lucas said that with a little training one can succeed in becoming quite quick at the manoeuvre (ii) above. By making use of a 127 x 127 chessboard, this was how Lucas performed his test on Mjio7. The advantage of not having to write FACTORING INTEGERS BEFORE COMPUTERS 493 anything down (contrary to Lehmer’s criticism in [71]) is to some degree offset by having nothing left at the end of the process but an answer. If an error were made, it would be difficult to detect. Depending on how quickly Lucas could execute the operations needed to perform this test, we estimate that it must have taken between 170-300 hours for him to complete it. This explains why he only performed this test of Mj27 a single time (see [112, p. 152]), and this may be why he was a little unsure of his result, but we’ll discuss this more fully in §5. One thing that is very striking about Lucas’ technique is how easy it should be to mechanize (and how much more accurate the results would be if it were). Certainly, Lucas thought so. In several of his papers [103, 105, 106, 107]; and [114, p. 305] he mentions the possibility of constructing a machine for doing this. For example in [103] he says: The construction of this mechanism allows for the rapid calcu- lation in the binary number system of residues of the V;, with respect to the number whose decomposition we are seeking. It is based on the preceding theorems and the mathematical laws of the geometry of weaving. In [106] he goes so far as to say: T have conceived ... the plan of a mechanism which allows ... for the determination of prime numbers having a thousand digits in the decimal system. The reference to the geometry of weaving is not as outlandish as it may seem. Lucas knew a great deal about weaving and wrote or presented several papers on this subject. Also, there were mechanisms in existence at that time which did allow for the construction of a fabric with the properties of the chessboard representation of the square of an integer (mod M,,) discussed above. In this representation a 1 might be denoted by a vertical thread passing over a horizontal one, whereas a zero would then be represented by a vertical thread passing under a horizontal one. Nevertheless, by the time Lucas published in 1878 his main work [114] on the Lucas Functions, his claims are much more subdued. Also, in his major paper on the geometry of weaving [119] (see [126] for a French translation) he makes no mention of using his ideas for constructing a machine. However, he never forgot these ideas, and in 1887 he says [121]: I will add that Mr. Genaille is currently constructing for me a machine that will enable us to {find all primes of the form 2” — 1] which have no more than 150 digits. Henri Genaille was a very prolific inventor of calculating mechanisms. Lucas praises him very warmly in his paper on calculating devices, which was reprinted in Vol. III of Récréations [125]. He is credited with constructing over 28 such devices in [129], all of which were donated in 1886-1888 to the Conservatoire National des Arts et Métiers in Paris. Also, he and Lucas worked together on a number of various computing devices (see [2]), and in 1891 we learn in an all-too-brief mention [32] that he had constructed an Arithmetic Piano, a device 494 H. C. WILLIAMS AND J. O. SHALLIT which was to be used for determining primes of the form 2” — 1. We quote the article [32] in full: The Arithmetic piano allows one to put into practice the method formulated by Mr. E. Lucas, at the Congress of Clermont- Ferrand, for the verification of large prime numbers. By the simple manoeuvering of some pegs, the verification of prime numbers of the form 2” — 1 is reduced in the greater number of cases to a labour of a few hours. This machine, which can manage to carry out automatically calculations of the greatest importance, will effect one day the realization of a calculating machine which performs arithmetic operations by itself. We have currently no idea what happened to this machine. Unfortunately, Lucas died at the early age of 49 a few weeks after the meeting at which the machine was exhibited and nothing seems to have been heard about it since. Gérardin [40], writing in 1912, claimed that Genaille had not constructed anything, but this is certainly not the sense of [31], where it is explicitly stated that the machine was admired by all the members of the session. Indeed, in view of the facts that 1) Genaille was a skilled fabricator of calculation machines and 2) that he had been working on this device for a period of about 4 years, it is difficult to believe that he would have discussed a nonexistent mechanism. However, it is possible that the device was not in a completely finished state. Very likely the machine was in the possession of Genaille when Lucas died, and there being no further use for it, Genaille probably abandoned the project. We wonder if somewhere in France this machine might still exist. It is curious to note that both Fauquembergue [25] in 1912 and Mason [128] in 1914 described devices based on Lucas’ ideas for testing the primality of M,,, devices which were based on the same multiplication technique of Cauchy [18], even though it appears that Mason was unaware of [18]. In the case of Fauquembergue, a device resembling a rather large slide rule was actually constructed and used. Mason’s device, which was more sophisticated in concept. than that of Fauquembergue, seems never to have been constructed. 5. Lucas and Mersenne The most difficult-to-answer of all the questions posed in §3 is (iv). This is because it does not appear that Lucas had ever settled this question in his own mind. What is particularly remarkable is his failure to mention the primality of My27 in several of his papers where it would have been appropriate, especially in his memoir [114], the notice of his works [118], or his book [122]. In many ways his doubts or caveats, expressed in one way or another in [102, 112, 120, 121, 123, 124] seem strange to us today. For, after going through all the labour necessary to find S;2¢ (mod Mj27) and finding it to be the particular residue zero, and considering all the possibilities for error, he would almost certainly FACTORING INTEGERS BEFORE COMPUTERS 495 have had the correct answer. The probability that it would be wrong is very remote indeed. However, this is not necessarily the way that Lucas thought about these matters. Remember that he had just discovered this test and did not have all the experience in these matters that we have today. He was evidently of two minds concerning his result; nowhere is this better illustrated than in his paper [120], written in 1886. This note seems to have been in response to one of Seelhoff [165] (see also [164]) in which, among other matters, it was stated that there were only eight perfect numbers known. Lucas replied that there were nine (his italics) such numbers and listed 2!26Mjo7 as one. Since from the time of Euler, it has been known that the only even perfect numbers are those of the form 2"-1M,,, where M,, is a prime, it is clear at this point that Lucas considered Mj27 a prime. However, on the next page of this same note he gave a list of