Michael Rabin

Michael Oser Rabin (September 1, 1931 to April 14, 2026) was an Israeli computer scientist, born in Breslau, Germany (now Wroclaw, Poland), who shared the 1976 ACM Turing Award with Dana Scott for a 1959 paper introducing the concept of nondeterministic automata, an idea that became foundational to theoretical computer science. He invented the Miller-Rabin primality test, a randomized algorithm that determines with overwhelming probability whether a large number is prime, and the Rabin cryptosystem, the first public key encryption scheme proven as hard to break as factoring large integers. With Richard Karp he also developed the Rabin-Karp string searching algorithm, which uses a rolling hash to find patterns in text efficiently.