Michael Rabin

Michael Rabin

Michael Rabin

Biographie

Naissance	1er septembre 1931 Wrocław
Décès	14 avril 2026 (à 94 ans) Jérusalem
Nom dans la langue maternelle	מִיכָאֵל עוזר רַבִּין
Nationalité	israélienne
Formation	École hébraïque Reali (en) (jusqu'en 1948) Université de Princeton (docteur en philosophie) (jusqu'en 1956) Université hébraïque de Jérusalem (baccalauréat ès sciences et master of science)
Activités	Informaticien, pédagogue, cryptographe, mathématicien, professeur d'université
Père	Israel Abraham Rabin (d)
Mère	Ester Rabin (d)
Fratrie	Chaim Rabin (en) (frère consanguin) Miriam Ben-Peretz (en)
Enfant	Tal Rabin

Autres informations

A travaillé pour	Université hébraïque de Jérusalem
Membre de	Académie américaine des sciences (1984) Royal Society (2007) Association for Computing Machinery (2021) Académie américaine des arts et des sciences Académie des sciences Société américaine de philosophie Académie israélienne des sciences et lettres
Conflit	Guerre israélo-arabe de 1948-1949
Directeur de thèse	Alonzo Church
Distinctions	Prix Turing (1976) Liste détaillée Prix Turing (1976) Prix Harvey (1980) Conférence Gibbs (1985) Prix Israël (1995) Doctorat honoris causa de l'université Bordeaux-I (1995) Charles Babbage Award (2000) Prix Paris-Kanellakis (2003) Prix EMET pour l'Art, la Science et la Culture (en) (2004) Gödel Lecturer (2004) Membre étranger de la Royal Society (2007) IACR Fellow (2009) Prix Dan-David (2010) ACM Fellow (2020) Prix Rothschild en sciences Docteur honoris causa de l'Institut Weizmann

Michael Oser Rabin, né le 1^er septembre 1931 à Breslau (Allemagne, aujourd'hui Wrocław en Pologne) et mort le 14 avril 2026^[1], est un informaticien et un logicien israélien. Il a été récipiendaire du prix Turing, la récompense la plus prestigieuse en informatique.

Michael Rabin est né fils de rabbin. Il a obtenu une maîtrise de l'université hébraïque de Jérusalem en 1953 et un doctorat de l'université de Princeton en 1956. La citation pour le prix Turing, attribué en 1976 conjointement à Michael Rabin et Dana Scott pour un article écrit en 1959, déclare qu'on a accordé la récompense : « Pour leur article « Finite Automata and Their Decision Problem » présentant l'idée des Automates finis non déterministes qui s'est révélée être un concept d'une énorme valeur. Leur article classique a été une source continue d'inspiration pour le travail qui s'est ensuivi dans ce domaine^[2]. » Les machines non déterministes sont devenues un concept clé dans la théorie de la complexité, en particulier avec la description des classes de complexité P et NP.

En 1957 et 1958, Michael Rabin a démontré que divers problèmes de théorie de groupes sont indécidables (ce sont les premiers du genre après ceux de Sergueï Adian en 1955). En 1969, il a démontré que l'arithmétique monadique du second ordre (avec k successeurs) est décidable^[3]. C'est le théorème de Rabin sur les arbres. En 1974, Michael Rabin a démontré avec Michel Fischer que l'arithmétique de Presburger a une complexité super-exponentielle. En 1975, il a été un pionnier des algorithmes probabilistes. Il a notamment inventé un algorithme randomisé, le test de primalité de Miller-Rabin, qui détermine très rapidement, mais avec une minuscule probabilité d'erreur, si un nombre est un nombre premier. Cet algorithme est essentiel à l'implémentation de la plupart des algorithmes de cryptographie asymétrique. Il a aussi écrit l'un des premiers algorithmes géométriques probabilistes, pour la recherche des deux points les plus rapprochés^[4]. En 1979, Michael Rabin a inventé le cryptosystème de Rabin, qui est le premier cryptosystème asymétrique dont la sécurité se réduit à la difficulté de la factorisation d'un nombre entier. En 1981, il a inventé la technique du transfert inconscient, permettant à un expéditeur de transmettre un message à un récepteur afin que celui-ci ait une certaine probabilité d'apprendre le message, tandis que l'expéditeur ne sait rien du succès du récepteur. En 1987, Michael Rabin, ainsi que Richard Karp, a créé un des algorithmes efficaces les plus connus de recherche de chaîne de caractères, l'algorithme de Rabin-Karp. Les recherches de Michael Rabin se concentrent sur la sécurité des systèmes d'information et il est ensuite professeur titulaire de la chaire d'informatique Thomas J. Watson à l'université Harvard et professeur d'informatique à l'université hébraïque de Jérusalem.

• 1976 : prix Turing
• 2004 : Gödel Lecturer avec une conférence intitulée Proofs persuasions and randomness in mathematics.