Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Test de primalité de Solovay-Strassen

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

Les concepts

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

où

est le symbole de Legendre.

Ainsi, pour déterminer si un entier 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 alors que p est composé. Un témoin d'Euler est une valeur de a telle que l'égalité ne soit pas vérifiée lorsque p est composé, c'est-à-dire que a est un témoin du fait que p soit composé.

À la différence du test de primalité de Fermat, pour chaque entier composé p au moins la moitié de tous les a de sont des témoins d'Euler.(?????) Par conséquent, il n'y a aucune valeur qui soit tout le temps un menteur, comme les nombres de Carmichaël le sont pour le test de Fermat.

Algorithme et performance

L'algorithme peut être écrit comme suit :

Entrées : n : variable entière 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 :

si x = 0 ou alors retourne composé

retourne probablement premier

En utilisant des algorithmes rapides d'exponentiation modulaire, la performance de cet algorithme est un O(k × log³p), 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 égale à 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.