マイケル・O・ラビン：コンピュータに「偶然」を馴染ませた男

10歳か11歳の頃、イギリス委任統治領パレスチナで、マイケル・ラビンは自分より年上の学生たちが解けなかった幾何学の問題を解いた。これは、他の誰もが絶対的な確実性を必要とすると想定していた問題に対して、エレガントで予想外の道を見つけ出すという、彼がその後の世紀をかけて発揮することになる知性の初期の兆候であった。オートマトン理論、暗号学、数論の全域にわたって繰り返されたラビンの特徴的な手法は、機械に推測やコイン投げを許可することが、信頼性を損なうどころか、むしろ機械をより強力にできるということに気づいた点である。この考えは、彼が最初に提案した当時は異端に近いものと見なされていた。

ブレスラウからパレスチナのラビの家庭へ

ラビンは1931年9月1日、当時ドイツ領で現在はポーランドのヴロツワフであるブレスラウで生まれた。ラビである父親は、ヨーロッパでこれから起こる最悪の事態を予見し、1935年に家族をパレスチナに移住させた。彼はハイファのヘブライ・リアリ・スクールに通い、後にテクニオンの教授となる数学者エリシャ・ネタニヤフに師事した。10代の頃にはすでに高度な数学セミナーに取り組んでいた。1953年にエルサレム・ヘブライ大学で数学の修士号を取得し、エミー・ネーターが提起した未解決問題を解決する論文を執筆。その後、渡米してプリンストン大学で博士号を取得し、1957年に論理学者アロンゾ・チャーチの指導の下で修了した。

推測できる機械

ラビンの最も重要な初期の論文は、ダナ・スコットと共同執筆し1959年に発表された「有限オートマトンとその決定問題」である。これは非決定性有限オートマトンという概念を導入した。これは、入力に遭遇した際に、効果的に自身の複数のコピーに分岐し、複数の計算経路を同時に追跡できる理論上の機械である。この論文は、これらの非決定性機械が、はるかに強力に見えるにもかかわらず、計算能力においては通常の決定性機械と完全に等価であることを証明した。これは、計算機科学が計算そのものを考える方法を再構築した基礎的な成果である。ACM（計算機学会）は、ラビンが30歳になる前に執筆したこの理論に対して、1976年にチューリング賞を授与した。

偶然に信頼性を教える

ラビンは、計算に意図的にランダム性を注入することで、信頼性を損なうことなく、より高速または単純にできるという、関連するより奇妙なアイデアに何度も立ち返った。1960年頃、ベル研究所で彼はコイン投げを使用して状態遷移を決定する確率的オートマトンを導入し、決定性機械よりも指数関数的に少ない状態で特定の言語を表現できることを示した。この直感は1975年にミラー-ラビン素数判定法へと結実した。これは、ゲイリー・ミラーによる以前の決定論的な研究に基づいたランダム化アルゴリズムであり、巨大な数が素数であるかどうかを判定する。これは現代のインターネットで使用される暗号システムを支えるほど高速かつ信頼性が高い。ラビンのバージョンは、ミラーが依存していた未証明の一般リーマン予想への依存を取り除いた点で注目に値する。2003年のカネラキス賞は、この分野へのミラー、ラビン、ロバート・ソロヴェイ、フォルカー・シュトラッセンの共通の貢献を称えた。

難解な数学から構築された鍵

ラビンの暗号学は素数判定を超えていた。1978年、彼はラビン暗号を考案した。これは、その安全性が大きな整数の因数分解の困難さと数学的に等価であると証明できる最初の非対称暗号スキームとして注目された。これは当時のほとんどの暗号システムが主張できたものよりも強力な保証であった。1981年、彼は「オブリビアス転送（Oblivious Transfer）」を定式化した。これは、送信者が受信者が実際に情報を受け取ったかどうかを知ることができないように情報を送信できる暗号プロトコルであり、安全なマルチパーティ計算の構成要素となった。1987年、リチャード・カープと共に、彼はラビン-カープ文字列検索アルゴリズムを共同開発した。これはローリングハッシュ技術であり、大量のテキスト内からパターンを見つける効率の良さから、現在でも学部レベルのアルゴリズムコースで教えられている。

2つの国にまたがるキャリア

ラビンの学術生活は、イスラエルとアメリカの間で並行して進んだ。エルサレム・ヘブライ大学では30代前半で上級講師から正教授に昇進し、数学研究所の所長を務め、1972年から1975年まで大学の学長を務めた。アメリカでは1981年からハーバード大学でゴードン・マッケイ教授職、次いでトーマス・J・ワトソン・シニア教授職を歴任し、MIT、バークレー、コロンビア大学で客員教授も務めた。彼は米国科学アカデミー、アメリカ芸術科学アカデミー、アメリカ哲学協会、フランス科学アカデミー、王立協会の会員に選出され、1995年にイスラエル賞、2010年にダン・デイヴィッド賞を受賞したほか、IEEEチャールズ・バベッジ賞やダイクストラ賞などの栄誉を受けた。

なぜマイケルは天才と呼ばれるのか

ラビンが天才とされる理由は、50年にわたるキャリアを通じて認識可能な特徴があるからである。それは、確実性を必要とすると想定されていた問題が、意図的にランダム性や非決定性を導入することで、より高速に解決できる、あるいはより強力にできることを繰り返し特定したことである。この洞察は、ランダム性が信頼できる計算の敵ではなくリソースとして扱われるようになった現在から見れば当然だが、当時はカテゴリエラーのように思われ、同時代の研究者に衝撃を与えた。オートマトン理論、素数判定、暗号プロトコル設計に独立して適用されたこの洞察は、それぞれが単独でも輝かしいキャリアを築けるほどの成果を生み出した。チューリング賞委員会やその後のカネラキス賞、バベッジ賞、ダイクストラ賞が称えたのは、まさにこの複数の成果である。記録上、これに対する深刻な反論はほとんどない。一部のチューリング賞受賞者の評判が1つの論文に基づいているのとは異なり、ラビンの評判は数十年にわたって独立して検証され、現在も使用されている成果に基づいている。ミラー-ラビン素数判定法は、教科書の中だけでなく、今日の暗号ライブラリの中で実際に実行されている。唯一の注意点があるとすれば、スコットとの最も有名な単一の論文が真のパートナーシップから生まれたという事実であり、この分野における最も鋭い個人の洞察であっても、通常は孤独な天才ではなくコラボレーションを通じて到達したということを思い出させる。

遺産

ラビンは2026年4月14日に94歳で死去した。晩年もハーバード大学とヘブライ大学の両方で名誉教授として籍を置いていた。娘のタル・ラビンも著名な暗号学者となり、家族のランダム性と秘密に対する特別な情熱を次世代へと引き継いだ。彼の名を冠したアルゴリズム（ミラー-ラビン、ラビン-カープ、ラビン暗号）は、コンピュータが数値を判定したり、文字列を検索したり、秘密を保持したりする必要がある場所で、現在も日常的に使用されている。これは、基礎的な理論計算機科学が、執筆から数十年経った今もなお目に見える形で日常の仕事を行っている稀なケースである。