Michael O. Rabin - Michael O. Rabin
Michael Oser Rabin | |
|---|---|
 | |
| Né |
1er septembre 1931 |
| Nationalité | israélien |
| mère nourricière |
Université hébraïque de Jérusalem ( MSc ) Université de Princeton ( PhD ) |
| Connu pour |
Test de primalité de Miller–Rabin Cryptosystème de Rabin Transfert inconscient Algorithme de recherche de chaînes de Rabin–Karp Automates finis non déterministes Algorithmes aléatoires |
| Récompenses |
Prix Turing (1976) Prix Paris Kanellakis (2003) Prix Israël Prix EMET Prix Harvey Prix Dan David Prix Dijkstra IEEE Computer Society Prix Charles Babbage |
| Carrière scientifique | |
| Des champs | L'informatique |
| Établissements |
Université Harvard Université hébraïque de Jérusalem Université Columbia |
| Thèse | Insolvabilité récursive des problèmes de théorie des groupes (1957) |
| Conseiller de doctorat | Église d'Alonzo |
| Doctorants | |
Michael Oser Rabin ( hébreu : מִיכָאֵל עוזר רַבִּין ; né le 1er septembre 1931) est un mathématicien et informaticien israélien et lauréat du prix Turing .
Biographie
Première vie et éducation
Rabin est né en 1931 à Breslau , en Allemagne (aujourd'hui Wrocław , en Pologne ), fils d'un rabbin . En 1935, il émigre avec sa famille en Palestine mandataire . Jeune garçon, il s'intéressait beaucoup aux mathématiques et son père l'envoya dans le meilleur lycée de Haïfa , où il étudia avec le mathématicien Elisha Netanyahu , qui était alors professeur au lycée.
Rabin est diplômé de l' école hébraïque Reali à Haïfa en 1948 et a été enrôlé dans l'armée pendant la guerre israélo-arabe de 1948 . Le mathématicien Abraham Fraenkel , qui était professeur de mathématiques à Jérusalem , intervint auprès du commandement de l'armée, et Rabin fut démobilisé pour étudier à l'université en 1949.
Il a obtenu un M.Sc. de l'Université hébraïque de Jérusalem en 1953 et un doctorat. de l'Université de Princeton en 1956.
Carrière
Rabin est devenu professeur agrégé de mathématiques à l' Université de Californie à Berkeley (1961-1962) et au MIT (1962-63). Avant de rejoindre l'Université Harvard en tant que professeur Gordon McKay d'informatique en 1981, il était professeur à l'Université hébraïque.
À la fin des années 1950, il a été invité pour un été à faire des recherches pour IBM au Lamb Estate dans le comté de Westchester, New York, avec d'autres mathématiciens et scientifiques prometteurs. C'est là que lui et Dana Scott ont écrit l'article "Les automates finis et leurs problèmes de décision". Bientôt, en utilisant des automates non déterministes, ils ont pu prouver à nouveau le résultat de Kleene selon lequel les machines à états finis acceptent exactement les langages réguliers.
Quant aux origines de ce qui allait devenir la théorie de la complexité computationnelle , l'été suivant, Rabin retourna au domaine Lamb. John McCarthy lui a posé une énigme sur les espions, les gardes et les mots de passe, que Rabin a étudié et peu de temps après, il a écrit un article, "Degré de difficulté de calcul d'une fonction et hiérarchie d'ensembles récursifs".
Les machines non déterministes sont devenues un concept clé dans la théorie de la complexité computationnelle, en particulier avec la description des classes de complexité P et NP .
Rabin est ensuite retourné à Jérusalem, faisant des recherches sur la logique et travaillant sur les fondements de ce qui sera plus tard connu sous le nom d' informatique . Il était professeur agrégé et directeur de l'Institut de mathématiques de l'Université hébraïque à 29 ans, et professeur titulaire à 33 ans. Rabin se souvient : « Il n'y avait absolument aucune appréciation du travail sur les problèmes de l'informatique. reconnaître le nouveau domaine émergent ».
En 1960, il a été invité par Edward F. Moore à travailler aux Bell Labs , où Rabin a introduit des automates probabilistes qui utilisent des tirages au sort afin de décider des transitions d'état à prendre. Il a montré des exemples de langages réguliers qui nécessitaient un très grand nombre d'états, mais pour lesquels on obtient une réduction exponentielle du nombre d'états si on passe aux automates probabilistes.
En 1969, Rabin a prouvé que la théorie du second ordre des n successeurs est décidable . Un élément clé de la preuve montrait implicitement la détermination des jeux de parité , qui se situent au troisième niveau de la hiérarchie de Borel .
En 1975, Rabin a terminé son mandat de recteur de l'Université hébraïque de Jérusalem et est allé au Massachusetts Institute of Technology aux États-Unis en tant que professeur invité. Gary Miller était également là et avait son test de temps polynomial pour la primalité basé sur l' hypothèse étendue de Riemann . Là-bas, Rabin a inventé le test de primalité de Miller-Rabin , un algorithme aléatoire qui peut déterminer très rapidement (mais avec une faible probabilité d'erreur) si un nombre est premier . La méthode de Rabin était basée sur des travaux antérieurs de Gary Miller qui résolvaient le problème de manière déterministe avec l'hypothèse que l' hypothèse de Riemann généralisée est vraie, mais la version du test de Rabin ne faisait pas une telle hypothèse. Des tests de primalité rapides sont essentiels à la réussite de la mise en œuvre de la plupart des cryptographies à clé publique, et en 2003, Miller, Rabin, Robert M. Solovay et Volker Strassen ont reçu le prix Paris Kanellakis pour leurs travaux sur les tests de primalité.
En 1976, il a été invité par Joseph Traub à se rencontrer à l'Université Carnegie Mellon et a présenté le test de primalité. Après avoir donné cette conférence, Traub avait dit : « Non, non, c'est révolutionnaire, et ça va devenir très important.
En 1979, Rabin a inventé le cryptosystème Rabin , le premier cryptosystème asymétrique dont la sécurité s'est avérée équivalente à l'intransigeance de la factorisation d'entiers .
En 1981, Rabin a réinventé une variante faible de la technique du transfert inconscient inventée par Wiesner sous le nom de multiplexage, permettant à un émetteur de transmettre un message à un récepteur où le récepteur a une probabilité comprise entre 0 et 1 d'apprendre le message, avec le l'expéditeur ignorait si le destinataire était en mesure de le faire.
En 1987, Rabin, en collaboration avec Richard Karp , a créé l' un des efficaces les plus connus des algorithmes de recherche de chaîne , l' algorithme de recherche de chaîne Rabin-Karp , connu pour son hachage de roulement.
Les recherches les plus récentes de Rabin se sont concentrées sur la sécurité informatique. Il est actuellement professeur d'informatique Thomas J. Watson Sr. à l'Université Harvard et professeur d'informatique à l'Université hébraïque . Au cours du semestre de printemps 2007, il a été professeur invité à l'Université Columbia pour enseigner l' introduction à la cryptographie .
Prix et distinctions
Rabin est membre étranger de l' Académie nationale des sciences des États-Unis , membre de l' Académie française des sciences et membre étranger de la Royal Society .
En 1976, le prix Turing a été décerné conjointement à Rabin et Dana Scott pour un article rédigé en 1959, dont la citation indique que le prix a été décerné :
Pour leur article conjoint "Finite Automata and Their Decision Problems", qui a introduit l'idée de machines non déterministes, qui s'est avérée être un concept extrêmement précieux. Leur article classique (Scott & Rabin) [ sic ] a été une source continue d'inspiration pour les travaux ultérieurs dans ce domaine.
En 1995, Rabin a reçu le Prix Israël , en informatique. En 2010, Rabin a reçu le prix Dan David de l'Université de Tel Aviv (catégorie "Avenir"), conjointement avec Leonard Kleinrock et Gordon E. Moore , pour l'informatique et les télécommunications. Rabin a reçu un doctorat honorifique en sciences de l'Université Harvard en 2017.
Voir également
- Transfert inconscient
- automate de Rabin
- Empreinte Rabin
- Hyper-cryptage
- Liste des lauréats du prix Israël