Test de primalité de Solovay-Strassen

Un article de Wikipédia, l'encyclopédie libre.

Le test de primalité de Solovay-Strassen est un test probabiliste permettant de déterminer si un nombre impair est un nombre composé ou un nombre premier probable.

[modifier] Les concepts

Le mathématicien suisse Euler a démontré que pour tout nombre premier p impair,

\left(\frac{a}{p}\right) \equiv a^{p-1 \over 2}\ (p)

où

\left(\frac{a}{p}\right)

est le symbole de Legendre.

Ainsi, pour déterminer si un entier impair p donné est premier, nous pouvons nous assurer que pour un grand nombre de valeurs aléatoires de a, l’égalité est bien vérifiée. Si elle est fausse pour un certain entier a, alors nous savons que p n’est pas premier.

Cependant, tout comme avec le test de primalité de Fermat, il y a des menteurs. Une valeur a est appelée menteur d’Euler si l’égalité est vérifiée bien que p soit composé. Un témoin d’Euler est une valeur de a pour laquelle l’égalité n'est pas vérifiée, et donc a est un témoin du fait que p est composé.

À la différence du test de primalité de Fermat, pour chaque entier composé p au moins la moitié de tous les a de (\mathbb{Z}/p\mathbb{Z})^* sont des témoins d’Euler. Par conséquent, il n’y a aucune valeur de p pour laquelle tous les a sont des menteurs, comme les nombres de Carmichaël pour le test de Fermat.

[modifier] Algorithme et performance

L’algorithme peut être écrit comme suit :

Entrées : n : variable entière impaire dont on veut connaître la primalité ; k : variable qui représente le nombre de fois où la primalité va être testée.
Sortie : composé si n est composé, sinon probablement premier
répéter k fois :
choisir a au hasard entre 1 et n-1
x\leftarrow \left(\frac{a}{n}\right)
si x = 0 ou a^{\frac{n-1}{2}}\not\equiv x\ (n) alors retourne composé
retourne probablement premier

En utilisant des algorithmes rapides d’exponentiation modulaire, la performance de cet algorithme est un O(k × log3p), où k est le nombre de fois où nous essayons aléatoirement un entier a, et p est la valeur dont nous voulons examiner la primalité. La probabilité pour que l’algorithme échoue est inférieure à 2- k.

Dans les applications en cryptographie, si nous choisissons une valeur suffisamment grande de k, comme par exemple 100, la probabilité pour que l’algorithme échoue est si petite que nous pouvons employer le nombre premier dans des applications cryptographiques sans inquiétude.