Test de primalité Solovay-Strassen - Solovay–Strassen primality test

Le test de primalité de Solovay-Strassen , développé par Robert M. Solovay et Volker Strassen en 1977, est un test probabiliste pour déterminer si un nombre est composé ou probablement premier . L'idée derrière le test a été découverte par MM Artjuhov en 1967 (voir le théorème E dans l'article). Ce test a été largement remplacé par le test de primalité Baillie-PSW et le test de primalité Miller-Rabin , mais a une grande importance historique pour montrer la faisabilité pratique du cryptosystème RSA . Le test de Solovay-Strassen est essentiellement un test pseudo-premier d'Euler-Jacobi .

notions

Euler a prouvé que pour tout nombre premier p et tout entier a ,

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

où est le symbole Legendre . Le symbole de Jacobi est une généralisation du symbole de Legendre à , où n peut être n'importe quel entier impair. Le symbole de Jacobi peut être calculé en temps O ((log n )²) en utilisant la généralisation de Jacobi de la loi de réciprocité quadratique . $\left({\tfrac {a}{p}}\right)$ $\left({\tfrac {a}{n}}\right)$

Étant donné un nombre impair n, nous pouvons envisager si oui ou non la congruence

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

tient pour diverses valeurs de la "base" a , étant donné que a est relativement premier à n . Si n est premier alors cette congruence est vraie pour tout a . Donc, si nous choisissons des valeurs de a au hasard et testons la congruence, alors dès que nous trouvons un a qui ne correspond pas à la congruence, nous savons que n n'est pas premier (mais cela ne nous dit pas une factorisation non triviale de n ). Cette base a est appelée témoin d'Euler pour n ; c'est un témoin de la composition de n . La base a est appelée un menteur d'Euler pour n si la congruence est vraie alors que n est composé.

Pour chaque n impair composé , au moins la moitié de toutes les bases

a\in (\mathbb {Z} /n\mathbb {Z} )^{*}

sont des témoins (Euler) car l'ensemble des menteurs d'Euler est un sous-groupe propre de . Par exemple, pour , l'ensemble des menteurs d'Euler est d'ordre 8 et , et d'ordre 48. $(\mathbb {Z} /n\mathbb {Z} )^{*}$ ${\style d'affichage n=65}$ $=\{1,8,14,18,47,51,57,64\}$ $(\mathbb {Z} /n\mathbb {Z} )^{*}$

Cela contraste avec le test de primalité de Fermat , pour lequel la proportion de témoins peut être beaucoup plus faible. Par conséquent, il n'y a pas (impair) composite n sans beaucoup de témoins, contrairement au cas des numéros Carmichael pour le test de Fermat.

Exemple

Supposons que nous souhaitions déterminer si n = 221 est premier. On écrit ( n −1)/2=110.

Nous sélectionnons au hasard un a (supérieur à 1 et inférieur à n ) : 47. En utilisant une méthode efficace pour élever un nombre à une puissance (mod n ) telle que l' exponentiation binaire , nous calculons :

a ^{( n −1)/2} mod n = 47 ¹¹⁰ mod 221 = −1 mod 221
${\style d'affichage ({\tfrac {a}{n}})}$ mod n = mod 221 = -1 mod 221. ${\style d'affichage ({\tfrac {47}{221}})}$

Cela donne que, soit 221 est premier ou 47 est un menteur Euler pour 221. Nous essayons un autre hasard a , cette fois en choisissant un = 2:

a ^{( n −1)/2} mod n = 2 ¹¹⁰ mod 221 = 30 mod 221
${\style d'affichage ({\tfrac {a}{n}})}$ mod n = mod 221 = -1 mod 221. ${\style d'affichage ({\tfrac {2}{221}})}$

Par conséquent, 2 est un témoin d'Euler pour la composition de 221, et 47 était en fait un menteur d'Euler. Notez que cela ne nous dit rien sur les facteurs premiers de 221, qui sont en fait 13 et 17.

Algorithme et temps d'exécution

L'algorithme peut être écrit en pseudocode comme suit :

inputs: n, a value to test for primality
        k, a parameter that determines the accuracy of the test
output: composite if n is composite, otherwise probably prime

repeat k times:
    choose a randomly in the range [2,n − 1]
     $x\gets \left({\tfrac {a}{n}}\right)$ 
    if  $x = 0$  or  $a^{(n-1)/2}\not \equiv x{\pmod {n}}$  then 
        return composite
return probably prime

En utilisant des algorithmes rapides pour l'exponentiation modulaire , le temps d'exécution de cet algorithme est O( k ·log ³ n ), où k est le nombre de valeurs différentes de a we test.

Précision du test

Il est possible que l'algorithme renvoie une réponse incorrecte. Si l'entrée n est en effet premier, alors la sortie sera toujours correctement probablement premier . Cependant, si l'entrée n est composite, il est possible que la sortie soit probablement incorrecte prime . Le nombre n est alors appelé pseudo-premier d'Euler-Jacobi .

Lorsque n est impair et composite, au moins la moitié de tous les a avec pgcd( a , n ) = 1 sont des témoins d'Euler. Nous pouvons le prouver comme suit : soit { a ₁ , a ₂ , ..., a _m } les menteurs d'Euler et a un témoin d'Euler. Alors, pour i = 1,2,..., m :

(a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2} =a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}} \right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}.

Parce que ce qui suit est valable :

\left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_ {À droite),

maintenant nous savons que

(a\cdot a_{i})^{(n-1)/2}\pas \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\ pmod {n}}.

Cela donne que chaque a _i donne un nombre a · a _i , qui est aussi un témoin d'Euler. Ainsi, chaque menteur d'Euler donne un témoin d'Euler et le nombre de témoins d'Euler est donc supérieur ou égal au nombre de menteurs d'Euler. Par conséquent, lorsque n est composé, au moins la moitié de tout a avec pgcd( a , n ) = 1 est un témoin d'Euler.

Par conséquent, la probabilité d'échec est d'au plus 2 ^{− k} (comparez-la avec la probabilité d'échec pour le test de primalité de Miller-Rabin , qui est d'au plus 4 ^{− k} ).

Aux fins de la cryptographie, plus nous testons de bases a , c'est-à-dire si nous choisissons une valeur de k suffisamment grande , meilleure est la précision du test. Par conséquent, le risque que l'algorithme échoue de cette manière est si faible que le (pseudo) premier est utilisé en pratique dans les applications cryptographiques, mais pour les applications pour lesquelles il est important d'avoir un premier, un test comme ECPP ou le test de primalité de Pocklington devrait être utilisé qui prouve la primalité.

Comportement moyen

La limite 1/2 sur la probabilité d'erreur d'un seul tour du test de Solovay-Strassen est valable pour toute entrée n , mais les nombres n pour lesquels la limite est (approximativement) atteinte sont extrêmement rares. En moyenne, la probabilité d'erreur de l'algorithme est significativement plus faible : elle est inférieure à

2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right )

pour k cycles de l'essai, appliqué à uniformément aléatoire n ≤ x . Le même lié vaut également pour le problème connexe de ce qui est la probabilité conditionnelle de n étant composite pour un nombre aléatoire n ≤ x qui a été déclaré en premier k tours de l'épreuve.

Complexité

L'algorithme de Solovay–Strassen montre que le problème de décision COMPOSITE est dans la classe de complexité RP .

Les références

Lectures complémentaires

Solovay, Robert M. ; Strassen, Volker (1977). « Un test rapide de Monte-Carlo pour la primalité ». Revue SIAM sur l'informatique . 6 (1) : 84-85. doi : 10.1137/0206006 .Voir aussi Solovay, Robert M. ; Strassen, Volker (1978). "Erratum : Un test rapide de Monte-Carlo pour la primalité". Revue SIAM sur l'informatique . 7 (1) : 118. doi : 10.1137/0207009 .
Dietzfelbinger, Martin (2004-06-29). "Test de primalité en temps polynomial, des algorithmes aléatoires à "PRIMES Is in P " ". Notes de cours en informatique . 3000 . ISBN 978-3-540-40344-9.

Liens externes

Solovay-Strassen Implémentation du test de primalité Solovay-Strassen dans Maple

Languages

In other projects