Test de primalité de Solovay-Strassen

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le test de primalité de Solovay-Strassen, dû à Robert M. Solovay et Volker Strassen, est un test de primalité probabiliste permettant de déterminer si un nombre impair est un nombre composé ou un nombre premier probable.

Les concepts[modifier | modifier le code]

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

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

\left(\frac ap\right)

est le symbole de Legendre. Le symbole de Jacobi

\left(\frac an\right)

en est une généralisation pour n non nécessairement premier.

Ainsi, pour déterminer si un entier impair n donné est premier, on peut tester, pour un grand nombre de valeurs aléatoires de a, si la congruence

\left(\frac an\right) \equiv a^{n-1 \over 2}\mod n

est vérifiée. Si elle est fausse pour un certain entier a, alors on sait que n 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 n 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 n est composé.

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

Algorithme et performance[modifier | modifier le code]

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 2 et n – 1
x\leftarrow \left(\frac an\right)
si x = 0 ou a^{\frac{n-1}2}\not\equiv x\mod n alors retourne composé
retourne probablement premier

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

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


(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Solovay–Strassen primality test » (voir la liste des auteurs).