Test de primalité de Solovay-Strassen

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 composé ou premier. C'est un test probabiliste, ne garantissant la primalité du nombre testé qu'avec une certaine probabilité (qu'on peut rendre aussi proche de 1 que l'on veut).

Base mathématiqueModifier

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'EulerModifier

Le symbole de Legendre   est défini pour p premier par 0 si   est multiple de p, 1 si   est un carré modulo p et –1 sinon.

Soit n un entier impair supérieur à 2 et n =   sa décomposition en facteurs premiers. Alors, pour tout entier  , le symbole de Jacobi   est une généralisation du symbole de Legendre qui vaut :  , où les   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  . 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 testModifier

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

 

est satisfaite. Si elle est fausse pour un certain entier  , alors on sait que   n’est pas premier[2].

Cependant, tout comme avec le test de primalité de Fermat, il y a des « menteurs ». Une valeur   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   pour laquelle l’égalité n'est pas satisfaite, et donc   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   de   sont des témoins d’Euler. Par conséquent, il n’y a aucune valeur de n pour laquelle tous les   sont des menteurs, alors que c'est le cas pour les nombres de Carmichael dans le test de Fermat[2].

AlgorithmeModifier

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   au hasard entre 2 et n – 1
 
si x = 0 ou   alors retourne composé
retourne probablement premier

PerformancesModifier

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   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 à  , avec   (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[2].

Sous l'hypothèse de Riemann généraliséeModifier

Si l'hypothèse de Riemann généralisée, non démontrée en 2020, est vraie alors tout nombre composé   admet un témoin d'Euler inférieur à  . Le test de primalité Solovay-Strassen peut dans ce cas être adapté en un test déterministe de complexité  [2], donc polynomial en le nombre de chiffres de  [note 1].

Notes et référencesModifier

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

NotesModifier

  1. Le nombre de chiffres d'un nombre entier est de l'ordre de son logarithme.

RéférencesModifier

  1. (en) Henri Cohen, A Course in Computational Algebraic Number Theory [détail de l’édition], p. 29-31.
  2. a b c et d Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, , 648 p. (ISBN 978-2-916352-75-6), II. Nombres premiers, chap. 3.3. (« Autour du petit théorème de Fermat »), p. 212-213.

Articles connexesModifier