Lehmer-zeef
Meer info
- Gemaakt door
- Derrick N. Lehmer en Derrick H. Lehmer
- Uitgebracht
- 1926
- Type
- Getaltheoretische speciale-doelmachine
- Locatie
- University of California, Berkeley
De doelgebouwde machine van de getaltheorie: negentien fietskettingen die rondtolden tot de gaten in alle kettingen toevallig op één lijn lagen, wat betekende dat er een oplossing was.
Derrick Norman Lehmer en zijn zoon Derrick Henry bouwden in 1926 een machine om getallen te vinden die tegelijk aan een reeks congruenties voldoen, de kernbewerking bij zowel ontbinden in factoren als het bewijzen dat een groot getal priem is. Elke ketting was op een lengte gesneden die bij één modulus paste, met gaten geboord op de plekken waar de restklasse paste. Een lamp scheen door het geheel op een fotocel erachter, en zodra alle gaten op één lijn lagen kwam het licht erdoor en stopte de motor. Het waren fietskettingen om de weinig glamoureuze reden dat ze goedkoop en kant-en-klaar te krijgen waren.
De versie uit 1932 verving kettingen door tandwielen en haalde zo'n 5.000 getallen per seconde, sneller dan welke universele machine ook voor decennia, juist doordat hij maar één ding kon. De jongere Lehmer pakte het probleem in 1946 weer op en draaide getaltheorie op ENIAC in een weekend waarin de ballistiekmensen vrij waren. De les wordt met regelmatige tussenpozen opnieuw geleerd: zodra de zoekruimte groot genoeg is, verslaat doelgebouwde hardware altijd het algemene geval. FPGA's en ASIC's zijn dezelfde deal in ander materiaal.