Test de primalité de Solovay-Strassen

Infos
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.
Test de primalité de Solovay-Strassen

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.

Les concepts

Le mathématicien suisse Euler a démontré que pour tout nombre premier p impair, :\left(\frac\right) \equiv a^p-1 \over 2\ (p) où :\left(\frac\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/p\mathbb)^
- 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.

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\right) ::si x = 0 ou a^\frac\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. Solovay-Strassen de:Solovay-Strassen-Test en:Solovay-Strassen primality test vi:Kiểm tra Solovay-Strassen
Sujets connexes
Algorithmique   Cryptographie   Exponentiation modulaire   Leonhard Euler   Mathématicien   Nombre composé   Nombre de Carmichaël   Nombre premier   Nombre premier probable   Pierre de Fermat   Probabilité   Suisse   Symbole de Legendre   Test de primalité   Test de primalité de Fermat  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^