Prueba de primordialidad Solovay-Strassen

La prueba de primalidad de Solovay-Strassen , desarrollada por Robert M. Solovay y Volker Strassen en 1977, es una prueba probabilística para determinar si un número es compuesto o probablemente primo . La idea detrás de la prueba fue descubierta por MM Artjuhov en 1967 ^[1] (ver Teorema E en el artículo). Esta prueba ha sido reemplazada en gran medida por la prueba de primalidad de Baillie-PSW y la prueba de primordialidad de Miller-Rabin , pero tiene una gran importancia histórica para demostrar la viabilidad práctica del criptosistema RSA . La prueba de Solovay-Strassen es esencialmente una Prueba de pseudoprime de Euler-Jacobi .

donde está el símbolo de Legendre . El símbolo de Jacobi es una generalización del símbolo de Legendre a , donde n puede ser cualquier número entero impar. El símbolo de Jacobi se puede calcular en el tiempo O ((log n ) ²) utilizando la generalización de Jacobi de la ley de reciprocidad cuadrática . ${\ Displaystyle \ left ({\ tfrac {a} {p}} \ right)}$ ${\ Displaystyle \ left ({\ tfrac {a} {n}} \ right)}$

sostiene para varios valores de la "base" un , dado que una es relativamente primo a n . Si n es primo, entonces esta congruencia es verdadera para todo a . Entonces, si elegimos valores de a al azar y probamos la congruencia, tan pronto como encontremos una a que no se ajuste a la congruencia, sabremos que n no es primo (pero esto no nos dice una factorización no trivial de n ). Esta base a se denomina testigo de Euler para n ; es un testimonio de la composición de n . La base ase llama mentiroso de Euler para n si la congruencia es verdadera mientras que n es compuesta.

son testigos (de Euler) ya que el conjunto de mentirosos de Euler es un subgrupo adecuado de . ^[3] Por ejemplo, para , el conjunto de los mentirosos de Euler tiene el orden 8 y , y tiene el orden 48. $(\mathbb {Z} /n\mathbb {Z} )^{*}$ $n=65$ $=\{1,8,14,18,47,51,57,64\}$ $(\mathbb {Z} /n\mathbb {Z} )^{*}$

Esto contrasta con la prueba de primordialidad de Fermat , para la cual la proporción de testigos puede ser mucho menor. Por lo tanto, no hay n compuesto (impar) sin muchos testigos, a diferencia del caso de los números de Carmichael para la prueba de Fermat.

Seleccionamos aleatoriamente una a (mayor que 1 y menor que n ): 47. Usando un método eficiente para elevar un número a una potencia (mod n ) como la exponenciación binaria , calculamos: