Le test de primalité AKS
En août 2002, trois chercheurs indiens, Manindra Agrawal, Neeraj Kayal et Nitin Saxena, ont publié un article proposant un test déterministe de primalité dont le temps d'exécution est comparable à celui de Rabin–Miller (voir ci-dessous). Comme pour ce dernier, l'idée de base est une amélioration du petit théorème de Fermat. Plus précisément, en étudiant les coefficients binomiaux, on démontre que si a est premier avec p, alors p est premier si, et seulement si, les deux polynômes (X – a)p et Xp – a, à coefficients dans ? / p?, sont égaux, c'est-à-dire si (X – a)p = Xp – a (mod p).
Un test reposant sur cette identité demande l'évaluation de tous les coefficients du polynôme (X – a)p, ce qui demande un temps prohibitif. L'idée pour rendre ce test effectif est d'évaluer cette identité modulo un polynôme Xr – 1, c'est-à-dire tester si (X – a)p = Xp – a (mod Xr – 1, p).
Si p est premier, cette identité est vraie pour tout couple (a, r) ; la réciproque est malheureusement fausse. Les trois chercheurs indiens ont montré que, pour des valeurs de r convenables, il suffisait de tester l'identité précédente pour un certain nombre de valeurs de a pour assurer si p est premier ou non.
Le test de primalité de Miller
D'après le petit théorème de Fermat, une idée pour vérifier si un nombre p est premier est de tester si x p –1 = 1 (mod p) pour une valeur de x parmi 2, 3… p – 1. La programmation de ce test est simple et son temps d'exécution court. Malheureusement, il ne donne pas toujours le bon résultat : si le résultat du test est « vrai », il n'est pas certain que p soit premier. Ainsi, l'entier 341 passe ce test, alors qu'il est le produit de 11 par 31. Une idée pour tourner la difficulté est d'étudier la probabilité d'obtenir la réponse « vrai » alors que p n'est pas premier. Cette probabilité est extrêmement faible : la probabilité que la réponse soit « vrai » bien que p n'est pas premier pour un nombre choisi aléatoirement parmi les vingt-cinq milliards plus petits est d'environ 2 × 10–5.
Une idée simple est alors d'effectuer le test pour plusieurs valeurs de x. A priori, on diminue la probabilité d'erreur. Cette idée a été améliorée par Michael Rabin (né en 1931) et Gary Miller (né en 1948) à partir de la factorisation du polynôme X p –1 – 1. Elle aboutit à un test du type précédent, que l'on applique en utilisant un entier x. Si on le répète pour k valeurs premières de x, le test dit si un nombre est premier avec un risque d'erreur de l'ordre de 1 / 4k. Ce test est a priori probabiliste mais pour de « petits » nombres, il est facile d'en déduire un test déterministe.