Le processus algorithmique consistant à décider si un entier donné est premier, fournissant soit un certificat déterministe de primalité soit un verdict probabiliste indiquant que le nombre est premier avec grande probabilité.

Principe

Les tests de primalité exploitent des propriétés arithmétiques distinguant les nombres premiers des composés (petit théorème de Fermat, conditions de probable premier fort, identités polynomiales, propriétés de courbes elliptiques) et produisent soit une preuve sans ambiguïté soit un témoin aléatoire montrant que le nombre est presque certainement premier.

Démonstration

Exemples : tests déterministes en temps polynomial comme AKS (vérifiant une congruence polynomiale), algorithmes probabilistes tels que Miller–Rabin (test des bases de probable premier fort), et méthodes produisant certificats comme ECPP qui renvoient une preuve vérifiable ; par exemple Miller–Rabin filtre rapidement les composés, tandis que ECPP peut générer un certificat explicite pour de grands nombres premiers utilisés en cryptographie.

Mauvaise application

Se fier à un seul test de Fermat pour affirmer la primalité sans tenir compte des nombres de Carmichael ou des témoins composés ; utiliser un test probabiliste là où une preuve déterministe est requise ; ou appliquer des tests conçus pour des impairs à des entrées paires ou triviales sans prétraitement.

Conséquence

Des tests de primalité efficaces permettent la génération et la validation pratiques de grands nombres premiers pour les protocoles cryptographiques et la théorie algorithmique des nombres ; lorsqu'un certificat déterministe est fourni, on obtient une certitude absolue adaptée à la vérification formelle et aux preuves mathématiques.

Inversion

L'inversion est la factorisation entière : connaître la factorisation complète permet immédiatement de décider la primalité mais est en général beaucoup plus coûteux ; inversement, la primalité peut souvent être beaucoup moins coûteuse que la factorisation complète et fournir parfois des certificats sans factoriser.

Limite

Concerne la décision de primalité d'entiers fournis sous une représentation explicite ; exclut des tâches voisines mais distinctes comme la factorisation entière, la primalité d'entiers algébriques sans réduction à Z, ou des heuristiques dépourvues de bornes d'erreur prouvables sauf si elles sont explicitement probabilistes et quantifiées.

Tension sémantique

Tension entre tests probabilistes (rapides, avec probabilité d'erreur minime) et preuves déterministes (plus lentes mais certaines) ; tension aussi entre le test comme décision binaire et la production d'un certificat vérifiable — les deux atteignent l'objectif mais répondent à des besoins et garanties distincts.

Synthèse

Le test de primalité comprend des critères algorithmiques, allant de contrôles probabilistes rapides à des preuves déterministes plus lentes, qui décident si un entier est premier ; il équilibre rapidité et certitude selon les besoins d'application et distingue le problème de décision du problème plus difficile de la factorisation complète.