In this blog series, Leo Corry, author of A Brief History of Numbers, helps us understand how the history of mathematics can be harnessed to develop modern-day applications today. The final post in the series takes a look at the history of factorization and its use in computer encryption.
The American Mathematical Society held on October 1903 its regular meeting in New York City. The program announced a talk by Frank Nelson Cole (1861-1921), with the unpretending title of On the factorization of large numbers. In due course, Cole approached the board and started to multiply the number 2 by itself, step after step and without saying a word, sixty seven times. He then subtracted 1 from the result obtained. He went on to multiply, by longhand, the following two large numbers:
193,707,721 x 761,838,257,287.
Realizing that the two calculations agreed, an astonished audience offered an enthusiastic applause, while Cole returned to his seat and continued to remain silent. One can only guess how satisfied he was for having shown to his colleagues this little gem of calculation that he discovered after much hard work.
The number 267 – 1 is commonly known as the Mersenne number M67. The question whether a given Mersenne number of the form 2n – 1 is prime had attracted some attention since the seventeenth century, but it was only in the last third of the nineteenth century that Edouard Lucas (1842-1891) came up with an algorithm to test this property. The algorithm was improved in 1930 by Derrick Henry (Dick) Lehmer (1905-1991) and turned into a widely used tool for testing primality, the Lucas-Lehmer test. But it is one thing to know, with the help of this test, whether or not a certain Mersenne number is prime, but a much more difficult task is finding the factors of one such large number even if we know it to be composite. When asked in 1911 how long it had taken to crack M67, he reportedly answered: “three years of Sundays.” Little did he know how important and ubiquitous such calculations would become in the age of e-commerce.
Almost hundred years later, another remarkable factorization was achieved, this one involving much larger numbers. In 1997 a team of computer scientists, led by Samuel Wagstaff at Purdue University, factorized a 167-digit number, (3349 – 1)/2, into two factors of eighty and eighty-seven digits respectively. According to Wagstaff’s report, the result required about 100,000 computer hours. Quite a bit more than in Cole’s story. Wagstaff had previously been involved in many other remarkable computations. For instance, in 1978 he used a digital computer to prove that Fermat’s last theorem (FLT) is valid for prime exponents up to 125,000.
Factorization results such as those of Cole and Wagstaff will at the very least elicit a smile of approval on the side of anyone with a minimum of sympathy and appreciation for remarkable mathematical results. But when faced with the price tag (in terms of human time spent or computer resources used to achieve it), the same sympathetic listener (and by all means the cynical one) will immediately raise the question whether all this awful lot of time was worth spending.
Central to the mainstream conceptions of pure mathematics over the twentieth century was the idea that numerical calculations with individual cases is at best a preliminary exercise to warm up the mind and start getting a feeling for the situations to be investigated. Still nowadays, many a mathematician is proud of stressing his slowness in calculating and pointing out the mistakes he makes in restaurants when splitting a bill among friends. David Hilbert (1862-1943) one of the most influential mathematicians at the turn of the twentieth century, was clear in stating that from “the highest peak reached on the mountain of today’s knowledge of arithmetic” one should “look out on the wide panorama of the whole explored domain” only with the help of elaborated, abstract theories. He consciously sought to avoid the use of any “elaborate computational machinery, so that … proofs can be completed not by calculations but purely by ideas.”
But with the rise of electronic computing a deep change has affected the status of time-consuming computational tasks from the time of Hilbert and Cole to the time of Wagstaff, via Lehmer and up to our own days. If in 1903 Cole found it appropriate to remain silent about his result and its significance, in 1997 the PR department of Purdue University rushed to publish a press release announcing Wagstaff’s factorization result: “Number crunchers zero in on record-large number”. Wagstaff cared to stress to the press the importance of knowing the limits of our abilities to perform such large factorizations, arguing that the latter are “essential to developing secure codes and ciphers.”
General perceptions about the need, and the appropriate ways for public scrutiny of science, its tasks and its funding, changed very much in the period of time between 1903 and 1997, and this in itself would be enough to elicit different kinds of reactions to both undertakings. But above all, it was the rise of e-commerce and the need for secure encryption techniques for the Internet that brought about a deep revolution in the self-definition of the discipline of number theory in the eyes of many of its practitioners, and in the ways it could be presented to the public. Whereas in the past, this was a discipline that prided itself above all for its detachment from any real application to the affairs of the mundane world, over the last four decades it has turned into the showpiece of mathematics as applied to the brave new world of cyberspace security. The application of public-key encryption techniques, such as those based on the RSA cryptosystem, turned the entire field of factorization techniques and primarily testing, from an arcane, highly esoteric, purely mathematical pursuit into a most coveted area of intense investigation with immediate practical applications, and expected to yield enormous economic gains to the experts in the field.
Featured image credit: Transmediale 2010 Ryoji Ikeda Data Tron 1 by Shervinafshar. CC BY-SA 3.0 via Wikimedia Commons.