MICHAEL RABIN

PRIX TURING 1976

BIO
THEORY
HISTOIRE
TEST

Michael Rabin
Informaticien Israelien
né en 1931 à Breslau en Allemagne, maintenant Wrocław en Pologne

À partir de 1976, Michael O. Rabin découvre et popularise l’importance d’approches probabilistes dans la conception d’algorithmes. C’est ce qu’on appelle parfois l’aléatoirisation (randomisation, en anglais) —l’aléa est introduit volontairement dans le calcul. L’ordinateur peut avoir intérêt à jouer aux dés… Ce changement de paradigme de programmation apporte dans un nombre de domaines des gains spectaculaires. Il s’agit notamment des calculs arithmétiques, des structures de données classiques pour l’accès rapide à l’information, de la géométrie algorithmique, et de l’algorithmique distribuée. Ainsi une algorithmique probabiliste permet pour la première fois de déterminer la primalité (avec risque d’erreur inférieur à 10-100) de nombres de plusieurs centaines de chiffres : le système cryptographique RSA qui garantit quotidiennement la sécurité de plusieurs millions de transactions repose sur ces techniques. Dans un autre domaine, afin que des ordinateurs communiquent en réseau, il est avantageux de se départir de l’approche déterministe de la téléphonie classique et de résoudre les conflits d’accès tout simplement par tirages au sort: ces principes sont à la base des réseaux Ethernet et du protocole TCP régissant plus de 90% des échanges sur l’Internet.


Pour les trois grandes catégories de problèmes cités, il est clair qu’une démarche mathématique joue tout d’abord un rôle capital dans la formalisation des problèmes et la constitution d’un cadre de pensée. La recherche en optimisation combinatoire n’est plus la même —elle est infiniment plus structurée et fructueuse— après les travaux de Cook, Karp, et leurs successeurs. Les percées de Knuth et Rabin, relayées par une large part de la communauté des chercheurs informaticiens, ont changé la manière dont se conduit la recherche en algorithmique,en offrant des repères clairs dans ce qui ne serait autrement qu’une jungle de techniques. Les sciences mathématiques alimentent continûment l’algorithmique, en suscitant les principes de nouveaux algorithmes ou encore en permettant, via l’analyse d’algorithmes,les optimisations et dimensionnements fins qui sont nécessaires à de nombreuses applications informatiques. pauillac


Au mois de mars 2001,Michael Rabin, annonçait la mise au point d’un procédé de chiffrement inviolable, basé sur le chiffrement symétrique dont la clé n’est plus immuable. Cette clé éphémère repose sur un flux de données aléatoires envoyé de manière synchrone à deux correspondants.

Ce système n’est pour l’instant que théorique car il requiert un débit de transmission “de millions de millions de bits par seconde que seul un système satellitaire pourrait apporter” affirme Michael Rabin.


Lire le Dossier sur Israel et la Science Données et statistiques scientifiques