AccueilđŸ‡«đŸ‡·Chercher

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ématique

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

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 test

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].

Algorithme

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

Performances

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ée

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érences

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

Notes

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

Références

  1. (en) Henri Cohen, A Course in Computational Algebraic Number Theory [dĂ©tail de l’édition], p. 29-31.
  2. 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 connexes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.