Lehmer sieve

14 min read Original article ↗

From Wikipedia, the free encyclopedia

A Lehmer sieve – a primitive digital computer once used for finding primes and solving simple Diophantine equations.

Lehmer sieves are mechanical devices that implement sieves in number theory. Lehmer sieves are named for Derrick Norman Lehmer and his son Derrick Henry Lehmer. The father was a professor of mathematics at the University of California, Berkeley at the time, and his son followed in his footsteps as a number theorist and professor at Berkeley.[1]

A sieve in general is intended to find the numbers which are remainders when a set of numbers are divided by a second set. Generally, they are used in finding solutions of Diophantine equations or to factor numbers. A Lehmer sieve will signal that such solutions are found in a variety of ways depending on the particular construction.[2]

The first Lehmer sieve in 1926 was made using bicycle chains of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical switches, and when all the switches were closed simultaneously, creating a complete electrical circuit, a solution had been found. Lehmer sieves were very fast, in one particular case factoring 2 93 + 1 = 3 × 3 × 529510939 × 715827883 × 2903110321 {\displaystyle 2^{93}+1=3\times 3\times 529510939\times 715827883\times 2903110321} in 3 seconds.[3] The original is lost, but an early-1980s reconstruction is at the Computer History Museum.[4]

Built in 1932, a device using gears was shown at the Century of Progress exposition in Chicago. These had gears representing numbers, just as the chains had before, with holes. Holes left open were the remainders sought. When the holes lined up, a light at one end of the device shone on a photocell at the other, which could stop the machine, allowing the observation of a solution. This incarnation allowed checking of five thousand combinations a second.[5]

In 1936, a version was built using 16 mm film instead of chains, with holes in the film instead of rods. Brushes against the rollers would make electrical contact when the hole reached the top. Again, a full sequence of holes created a complete circuit, indicating a solution.[6]

Several Lehmer sieves[5][6][7] (and the Bicycle Sieve replica[4]) are on display at the Computer History Museum. Since then, the same basic idea has been used to design sieves in integrated circuits or software.[citation needed]

Early work independent of Lehmer

[edit]

In 1896 F. W. Lawrence published the paper "Factorisation of numbers".[8] In its final section it outlines a design for an automated, electromechanical digital computing device which could apply the sieving method described in the paper. In 1910 a French translation was published by André Gérardin in his journal Sphinx-Oedipe:[9] this sparked a number of efforts to build devices on the lines of Lawrence's description.[10]: 512 

In February 1912 Gérardin reported in Sphinx-Oedipe that Maurice Kraitchik had built a mechanical prime sieve. According to Hugh C. Williams and Jeffrey Shallit its design is "rather similar to that of Lawrence" (Kraitchik already knew about Lawrence's paper when his machine was announced, though he did not acknowledge a connection.)[10]: 512  According to Shallit, Williams and François Morain, while Kraitchik's machine "might have worked reasonably well at low speeds, it would very likely have been useless at higher speeds". In March Gérardin also announced the existence of two other machines, one designed by Pierre Carrisan[11] and the other by himself. But according to Shallit, Williams and Morain "[a]ll three of these early attempts to construct a sieve suffered from the same inadequacies: they existed only as roughly constructed prototypes, were rather inefficient, required the human eye to scan for solutions, and produced no significant results—apparently none whatsoever."[12]

However during 1913-14 Eugène-Olivier Carissan, who had previously built the machine of his brother Pierre's design, designed and built a new prototype. Its performance was encouraging and so a precision version was ordered from the Paris horologists Chateau Frères et Cie. World War I delayed production and so the final machine à congruences ("congruence machine") was only completed in 1919. This machine was electro-mechanical but hand-cranked. It was able to prove 1,321,442,641 prime in 15 minutes of operation and prove 18,405,321,661 prime in 1 hour of operation.[13] According to Williams and Shallit "[t]his seems to have been the first automatic sieve mechanism to have ever been successfully constructed."[10]: 512  Shallit, Williams and Morain judged the 1926 Lehmer sieve to be "in many ways much less sophisticated" (though in fact it is somewhat faster). Since 1994 the 1919 Carissan machine has been in the collection of the Musée des Arts et Métiers.[14][12][15][a]

It was displayed at the Société d'encouragement pour l'industrie nationale's large Paris exhibition of calculating machinery in June 1920.[16] Eugène-Olivier had plans for improvements including motor-driven operation, but it seems these were not carried out: both Carissan brothers died by 1925 and the machine fell into obscurity over time.[12] D. H. Lehmer did not hear of the Carissans until 1989. He was aware of Lawrence and Kraitchik by at least 1934, when he described their designs for machines as "impractical ... [though] theoretically interesting"[17] even though, according to Williams and Shallit, Lehmer's 1932 gears sieve "represents in many ways the fruition of their ideas".[10]: 513  Similarly Gérardin was, according to Richard F. Lukes, "apparently totally unaware of Lehmer's previous work" when he constructed a new number sieve in 1937. This was reported to be an electrically-powered, automatic device incorporating a printer. Based on a photograph[18] Lukes speculated that it was based on an adding machine.[19][20]

In 1945 and 1946 D. H. and Emma Lehmer gained early experience with the vacuum-tube digital computer ENIAC at the University of Pennsylvania.[21] In the next two decades D. H. Lehmer and others would devote significant attention to writing software sieves for general-purpose computers. However, on his return home to Berkeley Lehmer also decided to seek to build a fast special-purpose hardware sieve using vacuum tube logic. In an unpublished 1946 document he proposed a design for such a sieve, naming it the "Electronic Sieve": it would have been able to be reconfigured by plugging and unplugging logic modules. The proposal also lays out his idea for an "Acoustic Sieve" in which, in Lukes' words, "the periodic element would be a tube of ethylene glycol with a piezo-electric crystal at each end".[19]: 16–7 [22] Lehmer and Berkeley engineering professor Paul Morton did, at some point between 1946 and 1964, design and build all or part of a sieve using counters.[b] After about two years' work they gave up this effort and instead turned their attention to working with delay line memory.[c][23]: 451 

In 1962 D. G. Cantor, G. Estrin, A. S. Fraenkel and R. Turn proposed another electronic sieve: this one would have used shift registers and been capable of being connected to a general-purpose computer, but was never built.[19]: 18–9  [24]

The Delay Line Sieve

[edit]

Lehmer and Morton's DLS-127, the initial form of the Delay Line Sieve, began operations in 1965 or 1966.[25] The DLS-127 was built as an unsponsored educational project of Berkeley's Departments of Mathematics and Electrical Engineering at a cost of about US$2000 ($20,433 in ), including a total of about $150 ($1,532 in ) for its navy-surplus wire delay lines. The machine used the innate delay of delay-line memory to advantage, running a number of delay lines of different lengths in parallel and noting a solution when they all returned input data simultaneously. It also had vacuum-tube components.[26] Input was by means of a paper tape which was prepared by software on an IBM 7094 or a CDC 6400.[d] In the early 1970s the machine was upgraded with an additional six moduli and renamed the DLS-157: these new delays were implemented using shift registers rather than delay lines. The Delay Line Sieve ceased operations in 1975;[27][e] it is now in the collection of the Computer History Museum.[7]

  1. ^ Several images of the 1919 Carissan sieve can be seen by searching for 'carissan' in the image bank of the Musée des Arts et Métiers. Direct links to the images available as of June 2026 are as follow: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
  2. ^ Lehmer's 1976 account seems to suggest that shortly after he returned to Berkeley (which would have been in 1946) he began work with Morton on a single effort to build a valve-based sieve; that this resulted in a valve-based sieve built around two short counters; and that they abandoned this then immediately began a single effort to work with delay lines which produced the DLS-127 (apparently working by 1965, at the earliest). But the timing seems to make this unlikely, especially if Stephens and Williams are correct that the work on the counter sieve was "two years of effort". Relatedly, it's not clear (at least without seeing the document) if the "Electronic Sieve" concept in the 1946 proposal document had input from Morton or had much connection to the counter sieve which Lehmer ended up working on with Morton.
  3. ^ According to the paper of Lehmer's 1976 presentation to the International Research Conference on the History of Computing, he and Morton gave up on the counter-based sieve because "[t]he whole thing was a little too short on reliability" while in his in-person presentation he said that "we could get reliable results, fairly reliable, but the whole thing turned out to be a little bit too expensive to set up".
  4. ^ Lukes, Stephens and Williams and Rubinstein all say that an IBM 7094 was used to prepare the paper tapes, but in his 1982 Computer Museum talk Lehmer instead says that a CDC 6400 was used.
  5. ^ However Lehmer does not clearly confirm this in his 1976 talk.
  1. ^ Rubinstein, Richard (17 October 1982). "D.H. Lehmer's Number Sieves" (PDF). The Computer Museum Report. No. Spring 1983. The Computer Museum (published 1983). pp. 3–4. ISSN 0736-5438. Retrieved 31 May 2026.
  2. ^ The Computer Museum Report. No. Spring 1983. The Computer Museum (published 1983). 17 October 1982. p. 2. ISSN 0736-5438 https://tcm.computerhistory.org/reports/TCMReportSpring1983.pdf. Retrieved 31 May 2026. . Untitled, uncredited preamble to the "D.H. Lehmer's Number Sieves" article, on the preceding page
  3. ^ W. W. Rouse Ball (1960) Lehmer's Machine, in Mathematical Recreations and Essays, Macmillan, New York, pp. 61–62.
  4. ^ a b Canepa, Roberto; Kristoffy, Andrew; Rubinstein, Richard (1981). Lehmer Bicycle Chain Number Sieve. Computer History Museum. 102647620. Retrieved 13 June 2026. Note that this is an early-1980s reconstruction by others (mainly Roberto Canepa) of the Lehmer "bicycle chain sieve", by then already lost
  5. ^ a b Lehmer, D. H. Photoelectric Number Sieve Machine ("Gear Machine"). Computer History Museum. X85.82. Retrieved 13 June 2026.
  6. ^ a b Lehmer, D. H. Number Sieve Machine using 16 mm film. Computer History Museum. X87.82. Retrieved 13 June 2026.
  7. ^ a b Lehmer, D. H.; Morton, Paul. Delay line number sieve machine. Computer History Museum. X86.82. Retrieved 12 June 2026.
  8. ^ Lawrence, F.W. "Factorisation of numbers". Q. J. Pure Appl. Math. 28 (1): 285–31.
  9. ^ Sphinx-Oedipe (in French). 5: 98–121. 1910. French translation of Lawrence, F.W. "Factorisation of numbers". Q. J. Pure Appl. Math. 28 (1): 285–31.
  10. ^ a b c d Williams, H. C.; Shallit, J. O. (1994). "Factoring Integers Before Computers" (PDF). In Gautschi, Walter (ed.). Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics. Mathematics of Computation 50th Anniversary Symposium (Vancouver, BC, 9-13 August 1993). Proceedings of Symposia in Applied Mathematics. Vol. 48. American Mathematical Society. pp. 481–531. ISBN 978-0-8218-0291-5. MR 1314885. Retrieved 8 June 2026.
  11. ^ A photograph of Pierre Carissan's machine appears at Mouyssinat, Michel (2012). "Homo Calculus". Actes du colloque « Vers un Musée de l’Informatique et de la société Numérique en France ?? ». Vers un Musée de l’Informatique et de la société Numérique en France ? (in French). Paris. p. 4.
  12. ^ a b c Shallit, Jeffrey; Williams, Hugh C.; Morain, François (January 1995). "Discovery of a Lost Factoring Machine". Mathematical Intelligencer. 17 (3): 41–47. doi:10.1007/BF03024369.
  13. ^ Carissan, E. "Machine à résoudre des congruences". Bull. Soc. Encouragement Ind. Nat. 132. Société d'encouragement pour l'industrie nationale: 600–607. Retrieved 8 June 2026.
  14. ^ Carissan, Eugène-Olivier. Machine à résoudre les congruences de Carissan. Musée des Arts et Métiers. 43048-0000-.
  15. ^ Mouyssinat, Michel (2012). "Homo Calculus". Actes du colloque « Vers un Musée de l’Informatique et de la société Numérique en France ?? ». Vers un Musée de l’Informatique et de la société Numérique en France ? (in French). Paris. p. 4.
  16. ^ Lemaire, E. "Exposition publique de machines à calculer anciennes et modernes". Bull. Soc. Encouragement Ind. Nat. 132. Société d'encouragement pour l'industrie nationale: 608–644. Retrieved 8 June 2026.
  17. ^ Lehmer, D. H. (December 1934). "A machine for combining sets of linear congruences". Mathematische Annalen. 109 (1): 661–667. doi:10.1007/BF01449160. ISSN 1432-1807. p. 663: The fact that a modulus is realized mechanically by a wheel has led computers, who have used the movable strip method, to imagine a machine which would do this work rapidly, without attention, and perform the exclusion of the numbers 1, 2, 3. … , using all the moduli at once. The literature contains at least two descriptions of such machines which, though impractical in their design, are theoretically interesting. As far as the writer knows, the first successful machine of this type was constructed by him in 19273). [...] ¶ 3) For a complete description of this machine, the reader may consult American Mathematical Monthly 35 (1928), 114—121.
  18. ^ The photo seems to be the same one reproduced at Mnémosyne. No. 17. IREM [fr] Paris 7 Denis Diderot. June 2002. p. 4. ISSN 1956-385X http://docs.irem.univ-paris-diderot.fr/up/publications/IPS02006.pdf. Retrieved 9 June 2026.
  19. ^ a b c Lukes, Richard F. (1995). A Very Fast Electronic Number Sieve (PDF) (Doctor of Philosophy in Computer Science thesis). Winnipeg, Manitoba, Canada: University of Manitoba. pp. 14–18. ISBN 0-612-13321-4. Retrieved 8 June 2026. (Thesis supervised by Hugh C. Williams.)
  20. ^ A. Gérardin. Machine à congruences (modèle 1937). In 70e Congrès des Sociétés Savantes de Paris et des Départements, Section des Sciences, pages 14,II, p.37. Gauthier-Villars, Paris, 1937
  21. ^ Markoff, John (9 May 2017). ""Unprogramming the ENIAC: Lehmer child's play". Computer History Museum. Retrieved 12 June 2026.
  22. ^ Lehmer, D. H. (1 December 1946), Preliminary proposal for the design and construction of the electronic sieve, U.C. Berkeley{{citation}}: CS1 maint: location missing publisher (link). Unpublished manuscript
  23. ^ Lehmer, D. H. "A History of the Sieve Process". In Metropolis, N.; Howlett, J.; Rota, Gian-Carlo (eds.). A History of Computing in the Twentieth Century. Academic Press. pp. 445–456. doi:10.1016/B978-0-12-491650-0.50030-7. ISBN 0-12-491650-3.
  24. ^ Cantor, D. G.; Estrin, G.; Fraenkel, A. S.; Turn, R. (1962). "A Very High-Speed Digital Number Sieve". Mathematics of Computation. 16: 141–154. doi:10.1090/S0025-5718-1962-0146990-0.
  25. ^ Lehmer, D. H. (1966). "An Announcement Concerning the Delay Line SIEVE DLS-127". Mathematics of Computation. 20: 644–646. doi:10.1090/S0025-5718-66-99911-X.
  26. ^ Rubinstein, Richard (17 October 1982). "D.H. Lehmer's Number Sieves" (PDF). The Computer Museum Report. No. Spring 1983. The Computer Museum (published 1983). pp. 3–4. ISSN 0736-5438. Retrieved 31 May 2026. p. 3: Later, he also built a sieve that used 16mm film, and another with vacuum tubes and delay lines.
  27. ^ Stephens, A. J.; Williams, H. C. (1990). "An open architecture number sieve". In Loxton, J. H. (ed.). Number Theory and Cryptography. London Mathematical Society Lecture Note Series. Cambridge University Press. pp. 38–75. doi:10.1017/CBO9781107325838. ISBN 9781107325838. OCLC 869934254.