Michael Oser Rabin, né le à Breslau (Allemagne, aujourd'hui Wrocław en Pologne) et mort le , est un informaticien et un logicien israélien. Il a été récipiendaire du prix Turing, la récompense la plus prestigieuse en informatique.
Biographie 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 :
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. Travaux 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. 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. 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.
Prix et distinctions 1976 : prix Turing 2004 : Gödel Lecturer avec une conférence intitulée Proofs persuasions and randomness in mathematics. Notes et références
Notes
Références
Voir aussi
Articles connexes Test de primalité de Miller-Rabin Cryptosystème de Rabin Algorithme de Rabin-Karp Transfert inconscient Liens externes
Description courte dans le Information Science Hall of Fame à l'université de Pittsburgh The Past, Present and Future of Oblivious Transfer, workshop sur le transfert inconscient à l'université de Haïfa, 2005
Catégorie:Naissance en septembre 1931 Catégorie:Naissance à Breslau Catégorie:Étudiant de l'université hébraïque de Jérusalem Catégorie:Docteur de l'université de Princeton Catégorie:Professeur à l'université Harvard Catégorie:Professeur à l'université hébraïque de Jérusalem Catégorie:Professeur au Technion Catégorie:Enseignant à l'École polytechnique fédérale de Zurich Catégorie:Personnalité américaine de l'informatique Catégorie:Logicien israélien Catégorie:Universitaire israélien Catégorie:Personnalité en sécurité informatique Catégorie:Personnalité en informatique théorique Catégorie:Personnalité d'IBM Catégorie:Docteur honoris causa de l'Institut Weizmann Catégorie:Lauréat du prix Turing Catégorie:Lauréat du prix Paris-Kanellakis Catégorie:Lauréat du prix Israël Catégorie:Lauréat du prix Dijkstra Catégorie:Lauréat du prix Harvey (Technion) Catégorie:Lauréat du prix Dan-David Catégorie:Gödel Lecturer Catégorie:Tarski Lecturer Catégorie:Membre de l'Académie israélienne des sciences et lettres Catégorie:Membre de l'Académie américaine des arts et des sciences Catégorie:Membre de la Société américaine de philosophie Catégorie:Membre de l'Académie nationale des sciences Catégorie:Membre de l'Académie des sciences (France) Catégorie:Membre de la Royal Society Catégorie:Décès à 94 ans Catégorie:Décès en avril 2026 Catégorie:Décès à Jérusalem