Miller-Rabin primality test immediately came to mind. But apparently he improved Berlekamp's algorithm, and is responsible for the pumping lemma [1] as well.

I agree with other posters; Rabin deserves an HN black bar.

[1] Basically, the pumping lemma says if you feed a finite state machine a long enough input, the FSM must loop. You can delete the looping part of the input or insert extra copies of it; the FSM can't tell the difference, it has to give the same output. In theoretical computer science, the pumping lemma is usually introduced early, as the simplest example of a theorem that proves there are things that cannot be computed by a certain class of computing machines (FSMs).

Post reply on HN