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 Solovay et Volker Strassen, est un test de primalité, c'est-à-dire un procédé qui détermine si un nombre impair est un nombre composé ou un nombre premier. C'est un test probabiliste, ne garantissant la primalité du nombre testé qu'avec une certaine probabilité (qu'on peut rendre aussi grande que l'on veut).

Base mathématique[modifier | modifier le code]

Le test de Soloway-Strassen repose sur quelques bases de théorie des nombres , rappelées ci-dessous.

Symboles de Legendre et de Jacobi, et critère d'Euler[modifier | modifier le code]

Le symbole de Legendre \left(\frac{a}{p}\right) est défini pour p premier par 0 si a est multiple de p, 1 si a est un carré modulo p et -1 sinon.

Soit n un entier impair supérieur à 2 et n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} la décomposition de n en facteurs premiers. Alors, pour tout entier a, le symbole de Jacobi \left(\frac{a}{n}\right) est une généralisation du symbole de Legendre qui vaut : \left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k}, où les \left(\frac{a}{p_i}\right) sont des symboles de Legendre.

Pour le symbole de Legendre, c'est-à-dire pour tout nombre premier p impair, le critère d'Euler dit que \left(\frac ap\right) \equiv a^{p-1 \over 2}\mod p. C'est a fortiori vrai si on remplace le symbole de Legendre par le symbole de Jacobi. Or le symbole de Jacobi peut être calculé pour tout entier de manière rapide (à l'aide d'une généralisation simple de la loi de réciprocité quadratique)[1].

Principe du test[modifier | modifier le code]

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 satisfaite. 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 satisfaite bien que n soit composé. Un témoin d’Euler est une valeur de a pour laquelle l’égalité n'est pas satisfaite, 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, alors que c'est le cas pour les nombres de Carmichael dans le test de Fermat.

Algorithme[modifier | modifier le code]

L’algorithme peut être écrit comme suit :

Entrées : n : un entier impair dont on veut connaître la primalité ; k : le nombre maximum de fois où le symbole de Jacobi va être calculé.
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 x \not\equiv a^{\frac{n-1}2}\mod n alors retourne composé
retourne probablement premier

Performances[modifier | modifier le code]

En utilisant des algorithmes rapides d’exponentiation modulaire, la complexité en temps dans le pire cas de cet algorithme est un O(k × log3 n), où k est le nombre maximum de fois où l'on tire aléatoirement un entier a pour calculer un symbole de Jacobi avec lui, et n est la valeur dont on veut examiner la primalité. La probabilité pour que l’algorithme échoue, c'est-à-dire la probabilité que n soit composé sachant que l'algorithme dit qu'il est premier, est inférieure à \scriptstyle 2^{-m}\frac{1-a}{a}, avec \scriptstyle a = \frac{2}{ln(n)} (et non pas 2-m comme on le trouve chez certains auteurs, ce qui est en fait la probabilité que l'algorithme réponde que n est premier alors qu'il ne l'est pas. Il y a deux ordres de grandeurs entre ces deux probabilités pour des valeurs typiques de n !)

Dans les applications en cryptographie, si l'on choisit une valeur suffisamment grande de k, par exemple 100, la probabilité pour que l’algorithme se trompe est si petite que l'on peut considérer le nombre qui a résisté au test comme premier et l'utiliser dans des applications cryptographiques sans inquiétude.

À partir de 1980, le test de Solovay-Strassen a été remplacé en pratique par le test de primalité de Miller-Rabin, plus efficace, car reposant sur un critère analogue, mais ne donnant de faux positif qu'au plus une fois sur quatre lorsque n n'est pas premier.

Notes et références[modifier | modifier le code]

(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).

  1. (en) Henri Cohen, A Course in Computational Algebraic Number Theory, Berlin, Springer Science+Business Media,‎ (ISBN 3-540-55640-0), pp. 29-31

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]