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 / 4*k. Ce test est a priori* probabiliste mais pour de « petits » nombres, il est facile d'en déduire un test déterministe.