Test de Solovay-Strassen

El test de Solovay-Strassen, creado por Robert M. Solovay and Volker Strassen en 1977,​ es un test de primalidad probabilístico. Analiza si un número entero dado es primo, dando una respuesta segura en caso de que la respuesta sea negativa, mientras que si la respuesta es afirmativa lo hace con cierta probabilidad de error (tan baja como uno se proponga, según cómo aplique el test).

Históricamente tiene importancia ya que fue el algoritmo probabilístico para verificar la primalidad de un entero. ​ Además, lo hace con un tiempo de ejecución de orden polinomial, lo que permitió asegurar que el sistema criptográfico RSA puede utilizarse en la práctica. El test ya no se utiliza en general, ya que ha sido superado por el test de primalidad de Miller-Rabin.​

Conceptos matemáticos que utiliza el test

El símbolo de Legendre nos dice cuándo un entero a es un cuadrado módulo p, donde p es primo. La definición es la siguiente:

$\left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\mbox{, si }}p|a;\\1&{\mbox{, si }}a\in \mathbb {Z} _{p}^{*}{\mbox{ y existe }}c{\mbox{ tal que }}c^{2}\equiv a{\pmod {p}};\\-1&{\mbox{, si }}a\in \mathbb {Z} _{p}^{*}{\mbox{ y no existe }}c{\mbox{ tal que }}c^{2}\equiv a{\pmod {p}}.\end{array}}\right.$

El criterio de Euler afirma que $\left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}$.

El símbolo de Jacobi se define a partir del de Legendre. Si $a,n\in \mathbb {Z}$ y n es impar, según el teorema fundamental de la aritmética podemos descomponerlo como producto de primos $n=p_{1}^{\alpha _{1}}\ldots p_{t}^{\alpha _{t}}$. Definimos en este caso: $\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\ldots \left({\frac {a}{p_{t}}}\right)^{\alpha _{t}}$

Según la definición, para conocer $\left({\frac {a}{n}}\right)$ debemos saber la descomposición en producto de primos de n. Sin embargo, el cálculo del símbolo de Jacobi puede hacerse de forma eficiente (sin factorizar n) usando las siguientes propiedades:

(I) $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$ si $a\equiv b{\pmod {p}}$

(II) $\left({\frac {2}{n}}\right)=(-1)^{\frac {n^{2}-1}{8}}$ si n es impar,

(III) $\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)$

(IV) $\left({\frac {a}{n}}\right)=\left\{{\begin{array}{rl}-\left({\frac {n}{a}}\right)&{\mbox{ si }}a\equiv n\equiv 3{\pmod {4}}\\\left({\frac {n}{a}}\right)&{\mbox{ en otro caso}}\end{array}}\right.$

El algoritmo

Como acabamos de mencionar, si p es primo impar entonces $\left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}$ para todo $a\in \mathbb {Z}$. O sea que (utilizando el contrarrecíproco) si para un n dado encontramos a que no verifica esta congruencia entonces n no es primo. Esta es la idea del algoritmo de Solovay-Strassen. Debido a que calcular el símbolo de Jacobi puede hacerse en tiempo polinomial (gracias a las propiedades (I)-(IV)) y a que hacer potencias módulo n también se puede hacer en tiempo polinomial (gracias al algoritmo de exponenciación binaria), este test es rápido de efectuar.

Sin embargo, si ocurre que encontramos a tal que $\left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}$ no podemos afirmar que p es primo.

Lo que sí ocurre es lo siguiente: si n no es primo entonces al menos la mitad de los a naturales con 0<a<n verifican $\left({\frac {a}{n}}\right)\neq a^{\frac {n-1}{2}}{\pmod {p}}$. Es decir que si nuestro test consta de probar con k enteros a distintos entonces $\mathbb {P}$(el test dé mal | n no es primo)=1/2^k. ​

Esto hace que el test, si bien no determina si un n es primo, sí nos da con cierta certeza (grande si probamos con muchos a distintos) que lo sea.

Esquema del test

Entrada: n natural impar,

Salida: "n no es primo" o "n es un probable primo".

(1) Se elige a un natural al azar entre 2 y n-2.

(2) Se calculan $u=a^{\frac {n-1}{2}}{\pmod {p}}$ y $v=\left({\frac {a}{n}}\right)$.

(3) Si $u\neq v$, responde "n no es primo".

(4) Si u=v, responde "n es un probable primo".

Si repetimos el procedimiento varias veces y siempre respondió "n es un probable primo", entonces con probabilidad muy grande n es primo.

Ejemplo

Queremos determinar si n = 221 es primo. Escribimos (n−1)/2=110.

Elegimos al azar a = 47 < n. Calculamos:

• a^(n−1)/2 mod n  =  47¹¹⁰ mod 221  =  −1 mod 221
• $({\tfrac {a}{n}})$ mod n  =  $({\tfrac {47}{221}})$ mod 221  =  −1 mod 221.

Esto hace que el test responda "221 es un probable primo". Probamos con otro a escogido al azar, en este caso a = 2:

• a^(n−1)/2 mod n  =  2¹¹⁰ mod 221  =  30 mod 221
• $({\tfrac {a}{n}})$ mod n  =  $({\tfrac {2}{221}})$ mod 221  =  −1 mod 221.

Por lo tanto, obtenemos que 221 es un número compuesto.

Referencias

Bibliografía

• Koblitz, Neal (2006). A course in number theory and cryptography (en inglés) (segunda edición). Springer. ISBN 0-387-94293-9. 
• Stinson, Douglas (2006). Cryptography: theory and practice (en inglés) (tercera edición). Chapman & Hall/ CRC. ISBN 978-1-58488-508-5. 

Enlaces externos

• Algoritmos probabilísticos Solovay-Strassen en Java
• El test en Planetmath.org (en inglés)

• Datos: Q2296113