Майкл О. Рабин: Человек, который подружил компьютеры со случайностью

Примерно в десять или одиннадцать лет, в Палестине под британским мандатом, Майкл Рабин решил геометрическую задачу, которая поставила в тупик студентов гораздо старше его — это был ранний признак ума, который проведет остаток века, находя элегантные и неожиданные пути решения проблем, которые, как все остальные предполагали, требовали абсолютной уверенности. Фирменный прием Рабина, повторяющийся в теории автоматов, криптографии и теории чисел, заключался в том, чтобы заметить, что предоставление машине разрешения угадывать или подбрасывать монету может сделать ее более мощной, а не менее надежной — идея, которая считалась почти еретической, когда он впервые ее предложил.

От Бреслау до дома раввина в Палестине

Рабин родился 1 сентября 1931 года в Бреслау, тогда в Германии, а ныне Вроцлав, Польша. Его отец, раввин, перевез семью в Палестину в 1935 году, предвидя худшее, что должно было произойти в Европе. Он учился в еврейской школе Реали в Хайфе, занимаясь под руководством математика Элиши Нетаньяху, который позже стал профессором в Технионе, и уже в подростковом возрасте работал на семинарах по высшей математике. Он получил степень магистра математики в Еврейском университете Иерусалима в 1953 году, защитив диссертацию, которая решила открытую проблему, первоначально поставленную Эмми Нётер, прежде чем отправиться в США для получения докторской степени в Принстоне, которую он завершил в 1957 году под руководством логика Алонзо Чёрча.

Машина, которая может угадывать

Самая важная ранняя работа Рабина, написанная совместно с Даной Скоттом и опубликованная в 1959 году под названием «Конечные автоматы и проблемы их решения», ввела понятие недетерминированного конечного автомата — теоретической машины, которая при получении входных данных могла эффективно разветвляться на несколько своих копий и одновременно следовать нескольким возможным вычислительным путям. В статье было доказано, что эти недетерминированные машины, несмотря на то, что они казались гораздо более мощными, были в точности эквивалентны обычным детерминированным машинам в том, что они могли вычислять, — фундаментальный результат, который изменил то, как компьютерные науки думают о вычислениях в целом. Ассоциация вычислительной техники (ACM) присудила Рабину и Скотту премию Тьюринга в 1976 году именно за эту статью — высшую награду в области компьютерных наук за теоретическую работу, написанную Рабином, когда ему еще не было тридцати.

Обучение случайности быть надежной

Рабин снова и снова возвращался к связанной, более странной идее: что преднамеренное внедрение случайности в вычисления может сделать их быстрее или проще, не делая их ненадежными. В Bell Labs около 1960 года он представил вероятностные автоматы, которые использовали подбрасывание монет для принятия решений о переходах состояний, показав, что они могут представлять определенные языки с экспоненциально меньшим количеством состояний, чем любая детерминированная машина. Эта интуиция созрела в 1975 году в тест на простоту Миллера-Рабина, рандомизированный алгоритм — основанный на предыдущей детерминированной работе Гэри Миллера — для определения того, является ли огромное число простым, достаточно быстрый и надежный, чтобы лежать в основе систем шифрования, используемых в современном Интернете; версия Рабина примечательна тем, что устранила зависимость Миллера от недоказанной обобщенной гипотезы Римана. Премия Канеллакиса 2003 года признала общий вклад Миллера, Рабина, Роберта Соловея и Фолькера Штрассена в это направление работы.

Замки, построенные на сложной математике

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

Карьера, разделенная между двумя странами

Академическая жизнь Рабина проходила параллельно в Израиле и США. В Еврейском университете Иерусалима он прошел путь от старшего преподавателя до профессора в возрасте чуть более тридцати лет, возглавлял Институт математики и был ректором университета с 1972 по 1975 год. В США он занимал должность профессора Гордона Маккея, а затем профессора Томаса Дж. Уотсона-старшего в Гарварде с 1981 года, а также был приглашенным профессором в MIT, Беркли и Колумбийском университете. Он был избран членом Национальной академии наук США, Американской академии искусств и наук, Американского философского общества, Французской академии наук и Лондонского королевского общества, а также получил Премию Израиля в 1995 году и премию Дэна Дэвида в 2010 году, наряду с другими наградами, включая премию IEEE Чарльза Бэббиджа и премию Дейкстры.

Почему Майкла называют гением

Статус Рабина как гения основан на узнаваемом почерке на протяжении пятидесятилетней карьеры: неоднократное выявление того, что проблема, которая, как предполагалось, требует определенности, может быть решена быстрее или сделана более мощной путем преднамеренного введения случайности или недетерминизма — озарение, которое поначалу поразило современников как категориальная ошибка, поскольку случайность широко рассматривалась как враг надежных вычислений, а не как ресурс для них. Это озарение, независимо примененное к теории автоматов, тестированию на простоту и проектированию криптографических протоколов, принесло результаты, каждый из которых сам по себе ознаменовал бы значительную карьеру; создание нескольких таких результатов — это то, что комитет премии Тьюринга и серия последующих премий Канеллакиса, Бэббиджа и Дейкстры явно чествовали. В истории почти нет серьезных контраргументов: в отличие от некоторых лауреатов премии Тьюринга, чья репутация основана на одной статье, репутация Рабина построена на независимо проверенных результатах, которые используются десятилетиями — тест Миллера-Рабина сегодня работает внутри криптографических библиотек, а не только в учебниках. Если и есть какая-то оговорка, то только та, что его самая известная статья, написанная со Скоттом, возникла в результате подлинного партнерства, что напоминает о том, что даже самое острое индивидуальное озарение в этой области обычно достигалось через сотрудничество, а не через одинокий гений.

Наследие

Рабин скончался 14 апреля 2026 года в возрасте девяноста четырех лет, проведя свои последние годы в качестве почетного профессора как в Гарварде, так и в Еврейском университете. Его дочь, Таль Рабин, стала выдающимся криптографом, перенеся особое увлечение семьи случайностью и секретностью в новое поколение. Алгоритмы, носящие его имя — Миллер-Рабин, Рабин-Карп, криптосистема Рабина — остаются в активном, повседневном использовании везде, где компьютеру нужно проверить число, найти строку или сохранить секрет, — редкий случай фундаментальной теоретической компьютерной науки, которая продолжает выполнять видимую повседневную работу спустя десятилетия после того, как была написана.