Discovery of a lost factoring machine

Despite the importance of the work of Eugène Carissan and the remarkable machine he built, very few people were aware of his work. Perhaps this was because both Pierre and Eugène died within 5 years of the exhibition of the machine in Paris in 1920. Indeed, when D. H. Lehmer began to construct his first automatic sieve in 1926, he had never heard of Carissan's sieve, and he remained ignorant of it until 1989. Lehmer's 1926 sieve, which was in some ways much less sophisticated than Carissan's, made use of bicycle chains driven by an electric motor. It was his first attempt of many. Each time he built a new sieve, the most advanced technology was used: photoelectric cells in 1932,16-mm movie film in 1936, and delay lines in 1965 for the DLS-127 (later DLS-157). For an account of all of this, see [18]. One could be led to think that sieves are old-fashioned and outclassed by modern computers. As a matter of fact, sieve methods remained the fastest known method for factoring integers up to 1970. Sieve devices are still much faster than current software programs. For instance, Williams, et al. (see [16] and [18]) have constructed devices that can perform up to 2 x 10¹² trials per second, compared to 2,000,000 on a workstation. Modern sieve devices are no longer used for factoring purposes, because an approach based on more sophisticated mathematical ideas and massive distribution of programs on workstations is much more powerful (see [15]). We should also point out that another special-purpose factoring machine, which was not a sieve, was constructed by Smith and Wagstaff [17] in 1983. However, for other special problems, sieve devices still seem to be the only way. For example, Stephens and Williams [18] used their device to find pseudosquares, numbers that behave like squares modulo many small primes. This study could eventually lead to a very fast primality-proving algorithm, if some highly plausible (yet hard) conjecture in number theory were true. Although sieve machines are not used to factor integers anymore, the basic principle of sieving remains at the heart of the modern factoring methods such as the quadratic sieve method or the number field sieve algorithm. Thus sieving, which was known to Euclid, is still a powerful method used in everyday life of number-theorists.