Gary L. Miller

Le test de primalité présenté par Gary Miller en 1975 est le premier algorithme de test dont l'efficacité est prouvée, mais son efficacité est conditionnée par la véracité de l'hypothèse de Riemann qui, elle, n'est toujours pas prouvée. En 1976, Michael O. Rabin montre que par randomisation, on peut contourner l'hypothèse non prouvée. Le nouvel algorithme, appelé test de primalité de Miller-Rabin, est maintenant employé dans la pratique, par exemple pour la génération de clés dans l'algorithme de chiffrement RSA. Pour ce travail, Miller et Rabin constituent, avec Robert Solovay et Volker Strassen, le groupe des lauréats du prix Paris Kanellakis de 2003.

Miller a aussi apporté des contributions significatives au problème de l'isomorphisme de graphes, en identifiant des classes particulières où une solution efficace existe. Miller a traité, avec John Reif, le cas de graphes dont le genre et la valence sont bornés. Également avec John Reif, il conçoit la notion de « contraction parallèle d'arbres », qui est devenue une primitive fondamentale dans la conception d'algorithmes parallèles, avec de multiples application à des problèmes algébriques et de théorie des graphes.

En 1984, Miller change de domaine et travaille dans le domaine de l'analyse numérique, et plus généralement de calcul scientifique. Il s'intéresse aux algorithmes de maillage, et obtient, en 2010, avec Ioannis Koutis et Richard Peng, des résultats innovants qui aboutissent à l'algorithme le plus rapide connu, en théorie et en pratique, pour la résolution de systèmes linéaires symétriques à diagonale dominante. Ces systèmes interviennent en traitement d'image, algorithmique des réseaux, ingénierie informatique et simulation informatique de phénomènes physiques[1].

• Il est fait ACM Fellow en 2002[2].
• En 2003, il est lauréat du prix Paris Kanellakis de l'Association for Computing Machinery avec Michael O. Rabin, Robert Solovay et Volker Strassen, pour le test de primalité de Miller-Rabin.
• Il obtient le prix Donald E. Knuth en 2013[1].

• Riemann's Hypothesis and Tests for Primality. Texte de la thèse de Ph. D.
• Page personnelle de Gary Miller à Carnegie Mellon.
• Ressources relatives à la recherche :
  • (en) Digital Bibliography & Library Project
  • (en) Mathematics Genealogy Project