Where are the Tools for Your Job?

Posted on May 16, 2008
Filed Under Quote |

After taking an abstract algebra class, I decided to revisit something from my cryptography class and figure out how the Number Field Sieve works, since my final project was writing the quadratic sieve [side-note: if anyone wants the code for it, I'll throw it up on the site. Actual sieving was not a requirement, so it uses trial division. IIRC, it factors 20-digit numbers pretty quickly].

In the introduction to the paper, I found:

"Unfortunately we are unable to give a rigorous proof that [the listed runtime] is indeed the expected running time of the number field sieve. Consequently, this paper does not contain a rigorous mathematical result. In this context the following quote from Donald Knuth is of interest: `One of my mathematician friends told me he would be willing to recognize computer science as a worthwhile field of study, as soon as it contains 1000 deep theorems. This criterion should obviously be changed to include algorithms as well as theorems, say 500 deep theorems and 500 deep algorithms.’

The present paper describes a deep algorithm for the solution of a fundamental problem, and it depends on techniques that have not been of traditional use in this area. We therefore trust that it is of interest to theoretical computer scientists, and that they will appreciate the challenge posed by its rigorous running time analysis."

"The Number Field Sieve": Lenstra, Lenstra Jr., Manasse, Pollard. 1990. Copyright ACM.

The interesting Knuth chestnut aside, it’s important to note that even the famous mathematicians draw inspiration from different sources. This is the best argument for perpetually continuing one’s education, no matter your field of study: the more you know, the more tools you can use.

Integer factorization is ostensibly a number theory problem, but the tools for the job were found in abstract algebra. Where are the tools for your job?

How are you sure that an Object-oriented database doesn’t solve your problem better if you’ve never learned how to use one? How are you sure that you shouldn’t be writing your web application with Ruby on Rails instead of PHP? Maybe Erlang solves your scaling problems much easier than Java. Maybe those Lisp jerks were right all along.

A lot of different solutions have been introduced by a lot of smart people. There may be a good one you haven’t tried.

Popularity: 9% [?]

Comments

Leave a Reply