Michael Rabin
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de Michael O. Rabin (né en 1931 à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un récipiendaire du prix Turing, la récompense la plus prestigieuse dans le domaine. Rabin est né fils de rabbin. Il a reçu une maîtrise de l'Université hébraïque de Jérusalem en 1953 et un doctorat de l'université Princeton en 1956.
La citation pour le prix Turing, attribué en 1976 conjointement à 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" qui a présenté l'idée des machines non déterministes, qui s'est avérée être un concept d'une valeur énorme. Leur article classique a été une source continue d'inspiration pour le travail qui s'en est suivi dans ce domaine.
Les machines non déterministes sont devenues un concept clé dans la complexité algorithmique, en particulier avec la description des classes de complexité P et NP.
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é, entre zéro et un, d'apprendre le message, et que l'expéditeur soit ne sache rien du succès du récepteur.
En 1987, Rabin, ainsi que Richard Karp, a créé un des algorithmes efficaces les plus bien connus de recherche de chaîne de caractères, l'algorithme de recherche de chaîne de caractères de Rabin-Karp.
La recherche contemporaine de Rabin s'est concentrée sur la sécurité informatique. Il est actuellement le Professeur Thomas J. Watson Sr. d'informatique à l'Université Harvard et professeur d'informatique à l'Université hébraïque de Jérusalem.
[modifier] Voir aussi
- Test de primalité de Miller-Rabin
- Cryptosystème de Rabin
- Algorithme de recherche de chaîne de caractères de Rabin-Karp
- Transfert inconscient
[modifier] Liens externes
- Description courte dans le Information Science Hall of Fame à l'université de Pittsburgh
- Citation du prix ACM Turing
- Transfert inconscient
 |
Portail de la cryptologie – Accédez aux articles de Wikipédia concernant la cryptologie. |
