レーマーのふるい

Derrick Norman Lehmerと息子のDerrick Henryは、1926年に、連立合同式を同時に満たす数を探す機械を作った。因数分解にも、大きな数が素数であることの証明にも欠かせない操作である。各チェーンは一つの法に合わせた長さに切られ、剰余類が合う位置に穴が開けられていた。ランプの光が組み立て全体を通って背後の光電管に当たり、すべての穴が揃った瞬間に光が通り抜けてモーターが止まる。チェーンが自転車用だったのは、安くて既製品が手に入るという地味な理由による。

1932年版ではチェーンが歯車に替わり、毎秒約5,000個の数を処理した。汎用機がこれに追いつくのは何十年も先で、それは一つのことしかできないからこそ出せる速度だった。息子のLehmerは1946年にこの問題へ戻り、弾道計算の担当者が休んでいる週末のENIACで整数論の計算を走らせた。探索空間が十分に大きくなれば、専用ハードウェアが汎用のものに必ず勝つ。この教訓は一定の間隔で学び直されており、FPGAやASICは素材の違うだけの同じ取引である。