Factoring Machines

July 3, 2009 | Math | By: Mark VandeWettering

I’ve blogged about D. H. Lehmer’s factoring machines before. It’s fairly hard to convince those who aren’t pathologically interested in rather quirky bits of mathematics and computing that this collection of bicycle chains and sprockets is worthy of study, but I didn’t have much difficulty convincing my typical lunchtime companion Tom that they were interesting, so we were discussing it a bit yesterday.

In the current era of ubiquitous computing, it’s hard to imagine that there was a time when computation wasn’t automated or mechanized, but back in the 1920s and 1930s, it truly was revolutionary stuff. An actual theory of computation was still on the horizon through the work of Church and Turing. The Bombe and Colossus code breaking machines of WWII were still in the future. Tom and I were musing that the revolutionary work of Lehmer and Lehmer were all the more revolutionary because they were without precedent. We also wondered how their work might have influenced code breaking machinery in WWII. Were the gents at Bletchley Park aware of the work that the father/son duo were doing, and did it serve as some inspiration?

Well, I still don’t know. I’m going to go back and dig through some of my references later, but I did find a couple of interesting things.

According to Knuth (Semi-Numerical Algorithms, pg. 390) the Lehmers were not the first to propose a mechanical device for automating the sieving task. In 1896, Frederick Lawrence wrote a paper entitled “Factorisation of Numbers” which inspired three different prototypes. The first successful factoring machine was built by Carrisan in 1919, which you can read more about here. Very neat device.

While trying to dig up online references, I found Eran Tromer’s annotated taxonomy of special purpose cryptographic machines. Lots of very good references and insights that might help me understand the historical context of these computing devices.

Share Button
Be Sociable, Share!

Write a comment