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
Notes
- Le nombre de chiffres d'un nombre entier est de l'ordre de son logarithme.
Références
- (en) Henri Cohen, A Course in Computational Algebraic Number Theory [dĂ©tail de lâĂ©dition], p. 29-31.
- 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.