Test de primalitat de Solovay-Strassen

El test de primalitat de Solovay-Strassen, que va ser desenvolupat per Robert M. Solovay i Volker Strassen, és un algorisme aleatori per a determinar si un nombre és un nombre compost o és un nombre primer probable. Ha estat superat de llarg pel test de primalitat de Miller-Rabin, però té una importància històrica gran en mostrar la factibilitat pràctica del criptosistema RSA.

Conceptes

Euler va demostrar que per a qualsevol nombre primer p i qualsevol enter $a$,

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

on ${\bigl (}{\tfrac {a}{p}}{\bigr )}$ és el símbol de Legendre. El símbol de Jacobi és una generalització del símbol de Legendre a ${\bigl (}{\tfrac {a}{n}}{\bigr )}$ on n pot ser qualsevol enter senar. El símbol de Jacobi es pot calcular en temps O((log n)²) fent servir la generalització de Jacobi de la llei de la reciprocitat quadràtica.

Es pot calcular si es compleix o no la congruència

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

per a diversos valors de a. Si n és un nombre primer, llavors la congruència és veritat per a tot a. Així, si es trien valors de a aleatòriament i es prova la congruència, llavors, tan aviat com es trobi un a que no compleix la congruència, se sap que n no és primer (però això no dona una factorització trivial de n).

Es diu que a és un Euler testimoni si la congruència anterior amb el símbol de Jacobi no es compleix a a — és a dir que a és un testimoni de què n és un nombre compost. A diferència del test de primalitat de Fermat, per a cada nombre senar compost n pel capbaix la meitat de tots els

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

són (Euler) testimonis. Per tant no hi ha cap nombre compost senar sense que tingui munts de testimonis, al contrari del que passava amb els nombres de Carmichael en el test de Fermat. La probabilitat que falli el test de primalitat de Solovay-Strassen és com a màxim de 1/2^k, on k és el nombre de proves.

Algorisme i temps d'execució

L'algorisme es pot escriure tal com segueix:

Algorisme test de primalitat de Solovay-Strassen (Ordre de complexitat ${\mathcal {O}}(k\log ^{3}n)$)

Entrada: Un nombre natural n>1, el nombre k de cops que s'executa el test i que determina la seva fiabilitat. Sortida: COMPOST si n és compost y POSSIBLE PRIMER si n és un nombre primer probable. Fer per a j des de 1 fins a k : $a\gets$ Funció Genera_nombre_aleatori_en_interval$(1,n-1]\,\!$ $x\gets \left({\frac {a}{n}}\right)$ Si x = 0 o $\left(a^{{\left(n-1\right)}/{2}\;}{\bmod {n}}\right)\neq x$ llavors: Retorna COMPOST Retorna POSSIBLE PRIMER

Fent servir algorismes ràpids per a la exponenciació modular, el temps d'execució d'aquest algorisme és ${\mathcal {O}}(k\log ^{3}n)$, on k és el nombre de cops que es prova un nombre a aleatori, i n és el nombre del qual es vol saber si és o no primer. La probabilitat que l'algorisme falli és com a molt de 2^-k. Amb finalitats criptogràfiques si es tria un nombre prou gran per a k, com ara 100, la possibilitat que l'algorisme falli és tan petita que es pot fer servir el nombre com si fos primer sense cap por.

Comportament del cas mitjà

La fita de 1/2 a la probabilitat d'error de cada prova del test de Solovay–Strassen és certa per a totes les entrades, però els nombres n per als quals s'assoleix (aproximadament) la fita són extremadament rars. De mitjana, la probabilitat d'error de l'algorisme és força més petita: és més petita que $2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right)$ per a k proves del test, si s'aplica a nombres n ≤ x uniformement aleatoris. La mateixa fita s'aplica al problema (relacionat amb aquest) de quina és la probabilitat condicional de què n sigui compost per a un nombre n ≤ x triat a l'atzar condicionada a que hagi estat declarat primer en k proves del test.

Referències

• Solovay, Robert M. and Volker Strassen «A fast Monte-Carlo test for primality». SIAM Journal on Computing, vol. 6, 1, 1977, pàg. 84–85. DOI: 10.1137/0206006.

• Martin Dietzfelbinger, Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P" (section 6), Series: Lecture Notes in Computer Science, Vol. 3000