Michael O. Rabin

Michael O. Rabin: The Man Who Made Computers Comfortable With Chance

At around ten or eleven years old, in Mandate-era Palestine, Michael Rabin solved a geometry problem that had stumped students years older than him — a small early sign of a mind that would spend the rest of the century finding elegant, unexpected paths through problems everyone else assumed required brute certainty. Rabin's signature move, repeated across automata theory, cryptography, and number theory, was to notice that giving a machine permission to guess, or to flip a coin, could make it more powerful rather than less reliable — an idea considered close to heretical when he first proposed it.

From Breslau to a Rabbi's Household in Palestine

Rabin was born September 1, 1931, in Breslau, then in Germany and now Wrocław, Poland. His father, a rabbi, moved the family to Palestine in 1935, ahead of the worst of what was coming in Europe. He attended the Hebrew Reali School in Haifa, studying under the mathematician Elisha Netanyahu, who later became a professor at the Technion, and by his teens was already working through advanced mathematics seminars. He earned a master's degree in mathematics at the Hebrew University of Jerusalem in 1953, a thesis that resolved an open problem originally posed by Emmy Noether, before crossing to the United States for a doctorate at Princeton, completed in 1957 under the logician Alonzo Church.

A Machine That Can Guess

Rabin's most consequential early paper, written with Dana Scott and published in 1959 as "Finite Automata and Their Decision Problems," introduced the concept of the nondeterministic finite automaton — a theoretical machine that, on encountering an input, could effectively branch into multiple copies of itself and pursue several possible computational paths at once. The paper proved that these nondeterministic machines were, despite seeming far more powerful, exactly equivalent in what they could compute to ordinary deterministic ones, a foundational result that reshaped how computer science thinks about computation itself. The Association for Computing Machinery awarded Rabin and Scott the Turing Award in 1976 specifically for that paper — computer science's highest honor, for a piece of theory written when Rabin was not yet thirty.

Teaching Chance to Be Reliable

Rabin returned again and again to a related, stranger idea: that deliberately injecting randomness into a computation could make it faster or simpler, without making it untrustworthy. At Bell Labs around 1960 he introduced probabilistic automata that used coin tosses to decide state transitions, showing they could represent certain languages with exponentially fewer states than any deterministic machine. That intuition matured, in 1975, into the Miller-Rabin primality test, a randomized algorithm — building on prior deterministic work by Gary Miller — for determining whether an enormous number is prime, fast enough and reliable enough that it underpins encryption systems used across the modern internet; Rabin's version notably removed Miller's dependence on the unproven generalized Riemann hypothesis. The 2003 Kanellakis Award recognized the shared contribution of Miller, Rabin, Robert Solovay, and Volker Strassen to this line of work.

Locks Built From Hard Math

Rabin's cryptography went beyond testing primes. In 1978 he devised the Rabin cryptosystem, notable as the first asymmetric encryption scheme whose security could be proven mathematically equivalent to the difficulty of factoring large integers — a stronger guarantee than most cryptosystems of the era could claim. In 1981 he formalized oblivious transfer, a cryptographic protocol allowing information to be sent so that the sender cannot know whether the receiver actually obtained it, which became a building block for secure multi-party computation. In 1987, with Richard Karp, he co-developed the Rabin-Karp string-search algorithm, a rolling-hash technique still taught in undergraduate algorithms courses for its efficiency at finding a pattern inside a large body of text.

A Career Split Between Two Countries

Rabin's academic life ran in parallel tracks between Israel and the United States. At the Hebrew University of Jerusalem he rose from senior lecturer to full professor by his early thirties, chaired its Institute of Mathematics, and served as the university's rector from 1972 to 1975. In the United States he held the Gordon McKay Professorship and then the Thomas J. Watson Sr. Professorship at Harvard from 1981 onward, alongside visiting appointments at MIT, Berkeley, and Columbia. He was elected to the U.S. National Academy of Sciences, the American Academy of Arts and Sciences, the American Philosophical Society, the French Academy of Sciences, and the Royal Society, and won the Israel Prize in 1995 and the Dan David Prize in 2010, alongside honors including the IEEE Charles Babbage Award and the Dijkstra Prize.

Why Michael Is Called a Genius

Rabin's case for genius rests on a recognizable signature across a fifty-year career: repeatedly identifying that a problem assumed to require certainty could instead be solved faster, or made more powerful, by deliberately introducing randomness or nondeterminism — an insight that at first struck contemporaries as almost a category error, since randomness was widely treated as the enemy of reliable computation rather than a resource for it. That insight, applied independently to automata theory, primality testing, and cryptographic protocol design, produced results each of which alone would mark a substantial career; producing several is what the Turing Award committee and the string of later Kanellakis, Babbage, and Dijkstra prizes were explicitly honoring. There is little serious counter-case in the record: unlike some Turing laureates whose reputations rest on one paper, Rabin's is built on independently verified, still-used results across decades — the Miller-Rabin test runs inside cryptographic libraries today, not merely in textbooks. If there is a caveat, it is only that his most famous single paper, with Scott, came from a genuine partnership, a reminder that even the sharpest individual insight in this field typically arrived through collaboration rather than solitary genius.

Legacy

Rabin died April 14, 2026, at ninety-four, having spent his final years still associated with both Harvard and Hebrew University as an emeritus professor at each. His daughter, Tal Rabin, became a distinguished cryptographer in her own right, carrying the family's particular fascination with randomness and secrecy into a new generation. The algorithms bearing his name — Miller-Rabin, Rabin-Karp, the Rabin cryptosystem — remain in active, everyday use wherever a computer needs to test a number, search a string, or keep a secret, a rare case of foundational theoretical computer science still doing visible daily work decades after it was written.

Achievements

• Turing Award — 1976
• Affiliated with Harvard University, Columbia University and University of California, Berkeley
• Educated at Hebrew University of Jerusalem, Hebrew Reali School and Princeton University
• Worked as computer scientist, mathematician and cryptographer