Рабин, Михаэль

Михаэль Рабин родился в 1931 году в семье уроженца Проскурова, раввина Исраэля Аврахама Рабина в Бреслау (ныне Вроцлав), принадлежавшем тогда Пруссии. В 1935 году его семья эмигрировала в Палестину. В 1953 году он получил степень магистра наук, окончив учёбу в Еврейском университете в Иерусалиме. Три года спустя, в 1956 году, защитил диссертацию в Принстонском университете и стал доктором философии.

Занимаелся исследованиями в области компьютерной безопасности и преподаёт в Иерусалиме и Гарварде. Почётный профессор в следующих вузах:^[2]

• Университет Бордо (1996);
• Хайфский университет (1996);
• Открытый университет Израиля (почётный член, 1999);
• Университет Бен-Гуриона (2000);
• Вроцлавский университет (2007).

К его знаменитым ученикам относится Саарон Шелах, ныне профессор в Иерусалиме, лауреат премии Вольфа по математике.

Его дочь Таль Рабин руководит научной группой Cryptography and Privacy Research Group в компании IBM.

Скончался 14 апреля 2026 года на 95-м году жизни.

В 1969 году Рабин обобщил теорему Бьюхи на случай более одной функции следования, чем показал разрешимость соответствующей теории второго порядка. В ходе ведения доказательства он доказал детерминированность игр на чётность (англ. parity games)

В 1975 году Гари Миллер разработал новый тест простоты, который был модифицирован Рабином в 1980 году. Тест Миллера — Рабина — вероятностный полиномиальный алгоритм, способный очень эффективно, но с ненулевой вероятностью ошибки, проверить число на простоту. Четыре года спустя, Майкл Рабин разработал первую асимметричную криптосистему, сложность взлома которой сравнима с проблемой факторизации целых чисел.

В 1981 году Рабин изобрёл протокол передачи данных с забыванием (англ. oblivious transfer) — надёжную технику передачи информации, при которой отправитель не получает подтверждения того, дошло ли сообщение до получателя. В 1987 году, вместе с Ричардом Карпом, Рабин разработал знаменитый алгоритм поиска образца (подстроки) в строке.

• 1960 — Премия Вейцмана по точным наукам^[3].
• 1973 — Премия Ротшильда по математике^[3].
• 1976 — Премия Тьюринга совместно с Дана Скоттом «за работу „Finite Automata and Their Decision Problem“, в которой вводится понятие недетерминированных конечных автоматов, ставших несомненно полезной концепцией. Их труд стал постоянным источником вдохновения для дальнейшей работы в этой области»^[4] Недетерминированные конечные автоматы являются ключевым понятием в теории сложности вычислений, где с их помощью описывается класс NP.
• 1980 — Премия Харви^[3].
• 1985 — Гиббсовская лекция.
• 1995 — Государственная премия Израиля по математике.
• 2000 — Премия Чарльза Беббиджа от IEEE.
• 2001 — Мемориальные лекции Вейцмана.
• 2003 — Премия Париса Канеллакиса^[2].
• 2004 — Премия ЭМЕТ^[5].
• 2010 — Премия Дэна Дэвида.
• 2015 — Премия Дейкстры.