Michael O. Rabin : L'homme qui a réconcilié l'informatique avec le hasard

Vers l'âge de dix ou onze ans, dans la Palestine sous mandat britannique, Michael Rabin a résolu un problème de géométrie qui avait mis en échec des étudiants bien plus âgés que lui — un signe précoce d'un esprit qui passerait le reste du siècle à trouver des chemins élégants et inattendus à travers des problèmes que tout le monde supposait nécessiter une certitude absolue. La marque de fabrique de Rabin, répétée dans la théorie des automates, la cryptographie et la théorie des nombres, était de remarquer que donner à une machine la permission de deviner, ou de lancer une pièce, pouvait la rendre plus puissante plutôt que moins fiable — une idée considérée comme proche de l'hérésie lorsqu'il l'a proposée pour la première fois.

De Breslau à un foyer rabbinique en Palestine

Rabin est né le 1er septembre 1931 à Breslau, alors en Allemagne et aujourd'hui Wrocław, en Pologne. Son père, un rabbin, a emmené la famille en Palestine en 1935, avant le pire de ce qui allait arriver en Europe. Il a fréquenté l'école hébraïque Reali à Haïfa, étudiant sous la direction du mathématicien Elisha Netanyahu, qui est devenu plus tard professeur au Technion, et dès son adolescence, il travaillait déjà sur des séminaires de mathématiques avancées. Il a obtenu une maîtrise en mathématiques à l'Université hébraïque de Jérusalem en 1953, avec une thèse qui a résolu un problème ouvert posé à l'origine par Emmy Noether, avant de partir aux États-Unis pour un doctorat à Princeton, terminé en 1957 sous la direction du logicien Alonzo Church.

Une machine qui peut deviner

Le premier article important de Rabin, écrit avec Dana Scott et publié en 1959 sous le titre « Finite Automata and Their Decision Problems », a introduit le concept de l'automate fini non déterministe — une machine théorique qui, face à une entrée, pouvait effectivement se ramifier en plusieurs copies d'elle-même et poursuivre plusieurs chemins de calcul possibles à la fois. L'article a prouvé que ces machines non déterministes étaient, bien qu'elles semblent beaucoup plus puissantes, exactement équivalentes dans ce qu'elles pouvaient calculer aux machines déterministes ordinaires, un résultat fondamental qui a remodelé la façon dont l'informatique conçoit le calcul lui-même. L'Association for Computing Machinery a décerné à Rabin et Scott le prix Turing en 1976 spécifiquement pour cet article — la plus haute distinction en informatique, pour une théorie écrite alors que Rabin n'avait pas encore trente ans.

Apprendre au hasard à être fiable

Rabin est revenu encore et encore à une idée connexe et plus étrange : que l'injection délibérée de hasard dans un calcul pouvait le rendre plus rapide ou plus simple, sans le rendre indigne de confiance. Aux Bell Labs vers 1960, il a introduit des automates probabilistes qui utilisaient des lancers de pièces pour décider des transitions d'état, montrant qu'ils pouvaient représenter certains langages avec exponentiellement moins d'états que n'importe quelle machine déterministe. Cette intuition a mûri, en 1975, dans le test de primalité de Miller-Rabin, un algorithme randomisé — s'appuyant sur les travaux déterministes antérieurs de Gary Miller — pour déterminer si un nombre énorme est premier, assez rapide et fiable pour sous-tendre les systèmes de chiffrement utilisés sur Internet aujourd'hui ; la version de Rabin a notamment supprimé la dépendance de Miller à l'hypothèse de Riemann généralisée non prouvée. Le prix Kanellakis 2003 a reconnu la contribution partagée de Miller, Rabin, Robert Solovay et Volker Strassen à cette ligne de travail.

Des verrous construits à partir de mathématiques complexes

La cryptographie de Rabin est allée au-delà des tests de nombres premiers. En 1978, il a conçu le cryptosystème de Rabin, remarquable en tant que premier schéma de chiffrement asymétrique dont la sécurité pouvait être prouvée mathématiquement équivalente à la difficulté de factoriser de grands entiers — une garantie plus forte que la plupart des cryptosystèmes de l'époque ne pouvaient revendiquer. En 1981, il a formalisé le transfert inconscient, un protocole cryptographique permettant d'envoyer des informations de sorte que l'expéditeur ne puisse pas savoir si le destinataire les a réellement obtenues, ce qui est devenu une brique de base pour le calcul multipartite sécurisé. En 1987, avec Richard Karp, il a co-développé l'algorithme de recherche de chaîne Rabin-Karp, une technique de hachage glissant toujours enseignée dans les cours d'algorithmes de premier cycle pour son efficacité à trouver un motif dans un grand corps de texte.

Une carrière partagée entre deux pays

La vie académique de Rabin s'est déroulée sur des voies parallèles entre Israël et les États-Unis. À l'Université hébraïque de Jérusalem, il est passé de maître de conférences à professeur titulaire au début de la trentaine, a présidé son Institut de mathématiques et a été recteur de l'université de 1972 à 1975. Aux États-Unis, il a occupé la chaire Gordon McKay puis la chaire Thomas J. Watson Sr. à Harvard à partir de 1981, parallèlement à des postes de professeur invité au MIT, à Berkeley et à Columbia. Il a été élu membre de la National Academy of Sciences des États-Unis, de l'American Academy of Arts and Sciences, de l'American Philosophical Society, de l'Académie française des sciences et de la Royal Society, et a remporté le prix Israël en 1995 et le prix Dan David en 2010, ainsi que des distinctions incluant le prix IEEE Charles Babbage et le prix Dijkstra.

Pourquoi Michael est qualifié de génie

Le cas de Rabin en tant que génie repose sur une signature reconnaissable tout au long d'une carrière de cinquante ans : identifier à plusieurs reprises qu'un problème supposé nécessiter une certitude pouvait être résolu plus rapidement, ou rendu plus puissant, en introduisant délibérément du hasard ou du non-déterminisme — une idée qui a d'abord frappé ses contemporains comme une erreur de catégorie, car le hasard était largement traité comme l'ennemi d'un calcul fiable plutôt que comme une ressource. Cette idée, appliquée indépendamment à la théorie des automates, aux tests de primalité et à la conception de protocoles cryptographiques, a produit des résultats dont chacun suffirait à marquer une carrière substantielle ; en produire plusieurs est ce que le comité du prix Turing et la série de prix ultérieurs Kanellakis, Babbage et Dijkstra honoraient explicitement. Il y a peu de contre-arguments sérieux : contrairement à certains lauréats du prix Turing dont la réputation repose sur un seul article, celle de Rabin est construite sur des résultats vérifiés indépendamment et toujours utilisés au fil des décennies — le test de Miller-Rabin est exécuté aujourd'hui dans des bibliothèques cryptographiques, pas seulement dans des manuels scolaires. S'il y a une mise en garde, c'est seulement que son article le plus célèbre, avec Scott, est issu d'un véritable partenariat, un rappel que même l'intuition individuelle la plus pointue dans ce domaine est généralement arrivée par la collaboration plutôt que par le génie solitaire.

Héritage

Rabin est décédé le 14 avril 2026, à quatre-vingt-quatorze ans, ayant passé ses dernières années toujours associé à Harvard et à l'Université hébraïque en tant que professeur émérite dans chacune. Sa fille, Tal Rabin, est devenue une cryptographe distinguée à part entière, portant la fascination particulière de la famille pour le hasard et le secret dans une nouvelle génération. Les algorithmes portant son nom — Miller-Rabin, Rabin-Karp, le cryptosystème de Rabin — restent en usage actif et quotidien partout où un ordinateur a besoin de tester un nombre, de rechercher une chaîne ou de garder un secret, un cas rare d'informatique théorique fondamentale faisant toujours un travail quotidien visible des décennies après avoir été écrit.