Michael Rabin
Michael Oser Rabin (né en 1931 à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un logicien. Il a été récipiendaire du prix Turing, la récompense la plus prestigieuse en informatique.
Repères bibliographiques
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 machines 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'en est suivi dans ce domaine[1]. »
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, 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 Sergei Adian en 1955).
En 1969, Rabin a démontré que l'arithmétique monadique du second ordre (avec k successeurs) est décidable.
En 1974, Rabin a démontré avec Michel Fischer que l'arithmétique de Presburger a une complexité super-exponentielle.
En 1975, Rabin a 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.
En 1979, Rabin a inventé le cryptosystème de Rabin, qui est le premier cryptosystème asymétrique dont la sécurité se réduit à l'intractabilité de la factorisation d'un nombre entier.
En 1981, Rabin 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, 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 actuelles de Rabin se concentrent sur la sécurité des systèmes informatiques et il est actuellement professeur titulaire de la chaire d'informatique Thomas J. Watson Sr. à l'université Harvard et professeur d'informatique à l'université hébraïque de Jérusalem.
Notes et références
- Traduction libre de : (en) Citation du prix ACM Turing
Voir aussi
Articles connexes
- Test de primalité de Miller-Rabin
- Cryptosystème de Rabin
- Algorithme de Rabin-Karp
- Transfert inconscient
Liens externes
- (en) Description courte dans le Information Science Hall of Fame à l'université de Pittsburgh
- (en) The Past, Present and Future of Oblivious Transfer, workshop sur le transfert inconscient à l'université de Haïfa, 2005
Modèle:Publications informatique
- Naissance en 1931
- Naissance à Breslau
- Personnalité américaine en informatique
- Universitaire israélien
- Personnalité en sécurité informatique
- Personnalité en informatique théorique
- Étudiant de l'université hébraïque de Jérusalem
- Docteur de l'université de Princeton
- Professeur à l'université Harvard
- Professeur à l'université hébraïque de Jérusalem
- Professeur au Technion
- Docteur honoris causa
- Lauréat du prix Turing
- Lauréat du prix Paris Kanellakis
- Lauréat du prix Israël
- Membre de l'Académie israélienne des sciences et lettres
- Membre de la Société américaine de philosophie
- Membre de la National Academy of Sciences
- Membre de l'Académie des sciences (France)
- Membre de la Royal Society