Test de Solovay-Strassen

El test de primalidad de Solovay-Strassen, creado por Robert M. Solovay y Volker Strassen en 1977,^[1] 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 se desee, según cómo se aplique el test). La idea detrás de la prueba fue descubierta por M. M. Artjuhov en 1967 (véase el Teorema E en el documento del enlace que figura en la referencia siguiente).^[2].

Históricamente tiene importancia, ya que fue el algoritmo probabilístico para verificar la primalidad de un entero.^[3] 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.^[4]

Conceptos matemáticos que utiliza el test

Dado un número impar n se puede contemplar si se da o no la congruencia

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

que vale para varios valores de la "base" a, dado que a es un número coprimo con respecto a n. Si n es primo, entonces esta congruencia es verdadera para todo a. Entonces, si se elegen valores de a al azar y probamos la congruencia, entonces, tan pronto como se encuentra una a que no se ajusta a la congruencia, entonces se sabe que n no es primo (pero esto no determina una factorización no trivial de n). Esta base a se llama un testigo de Euler para n, dado que es un testigo de que n es un número compuesto. La base a se llama mentiroso de Euler para n si la congruencia es verdadera, mientras que n es compuesto.

Por cada impar compuesto n, al menos la mitad de todas las bases

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

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

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

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 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 se puede descomponer como un producto de primos $n=p_{1}^{\alpha _{1}}\ldots p_{t}^{\alpha _{t}}$ . Se define 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)$ se debe conocer 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 se acaba 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 se encuentra un 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 calcular 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 se encuentra un a tal que $\left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}$ , no se puede afirmar que p sea 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 el test consiste en probar k enteros a distintos, entonces $\mathbb {P}$ (el test dé mal | n no es primo)=1/2^k.^[6]

Esto hace que el test, si bien no determina si un n es primo, sí ofrece cierta certeza (grande si se prueba 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 {n}}$ 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

Supóngase que se desea determinar si n = 221 es primo. Entonces, se calcula (n+1)/2=110.

Se selecciona 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, se calcula:

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

Esto da que, o 221 es primo, o 47 es un mentiroso de Euler para 221. Se prueba otra a aleatoria, esta vez eligiendo a = 2:

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

Por lo tanto, 2 es un testigo de Euler de la composición de 221, y 47 es de hecho un mentiroso de Euler. Téngase en cuenta que esto no dice nada acerca de los factores primos de 221, que en realidad son 13 y 17.

Complejidad

El algoritmo de Solovay-Strassen muestra que el problema de decisión COMPUESTO está en el clase de complejidad RP.^[7]

Precisión de la prueba

Es posible que el algoritmo devuelva una respuesta incorrecta. Si la entrada n es de hecho un primo, entonces la salida siempre será correctamente probablemente primo. Sin embargo, si la entrada n es compuesta, entonces es posible que la salida sea incorrectamente probablemente prima. El número n se llama entonces número pseudoprimo de Euler-Jacobi.

Cuando n es impar y compuesta, al menos la mitad de todas las a con mcd(a,n) = 1 son testigos de Euler. Podemos probar esto de la siguiente manera: sean {a₁, a₂, ..., a_m} los mentirosos de Euler y a un testigo de Euler. Entonces, para i = 1,2,...,m:

(a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}.

porque se cumple lo siguiente:

\left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right),

y entonces se sabe que

(a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.

Esto da que cada a_i da un número a·a_i, que también es un testigo de Euler. Entonces, cada mentiroso de Euler da un testigo de Euler y, por lo tanto, el número de testigos de Euler es mayor o igual al número de mentirosos de Euler. Por lo tanto, cuando n es compuesto, al menos la mitad de todos los a con mcd(a,n) = 1 es un testigo de Euler.

Por lo tanto, la probabilidad de fallo es como máximo 2^−k (compárese con la probabilidad de fallo para el test de primalidad de Miller-Rabin, que es como máximo 4^−k).

A efectos criptográficos, cuantas más bases a se prueben, es decir, si se elege un valor suficientemente grande de k, mejor será la precisión de la prueba. Por lo tanto, la posibilidad de que el algoritmo falle de esta manera es tan pequeña que el (pseudo) primo se usa en la práctica en aplicaciones criptográficas. Pero para aplicaciones para las que es importante tener un primo, se debe usar una prueba como el ECPP o el test de Pocklington-Lehmer,^[8] capaces de dar una prueba de primalidad concluyente.

Comportamiento promedio

El límite 1/2 en la probabilidad de error de una sola ronda de la prueba de Solovay-Strassen se cumple para cualquier entrada n, pero esos números n para los que se alcanza (aproximadamente) el límite son extremadamente raros. En promedio, la probabilidad de error del algoritmo es significativamente menor, y de hecho, es menor que

2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right)

para k rondas de la prueba, aplicadas a n ≤ x uniformemente aleatorias.^[9]^[10] El mismo límite también se aplica al problema relacionado de cuál es la probabilidad condicional de que n sea compuesto para un número aleatorio n ≤ x que ha sido declarado primo en k rondas de la prueba.

Referencias

↑ Robert Solovay; Volker Strassen (1977). «A Fast Monte-Carlo Test for Primality». SIAM J. Comput 6: 84-85.
↑ Artjuhov, M. M. (1966–1967), «Certain criteria for primality of numbers connected with the little Fermat theorem», Acta Arithmetica 12: 355-364, MR 0213289 .
↑ Borges Hernández, Cruz Enrique (2005). Test de primalidad, el AKS (Tesis). Universidad de La Laguna. Consultado el 12 de agosto de 2015.
↑ Stinson, p. 186
↑ PlanetMath
↑ Koblitz, p.129
↑ R. Motwani; P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. pp. 417-423. ISBN 978-0-521-47465-8.
↑ Pocklington test on Mathworld
↑ P. Erdős; C. Pomerance (1986). «On the number of false witnesses for a composite number». Mathematics of Computation 46 (173): 259-279. JSTOR 2008231. doi:10.2307/2008231.
↑ I. Damgård; P. Landrock; C. Pomerance (1993). «Average case error estimates for the strong probable prime test». Mathematics of Computation 61 (203): 177-194. JSTOR 2152945. doi:10.2307/2152945.

Bibliografía

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

Enlaces externos

Implementación en Java del algoritmo
El test en Planetmath.org (en inglés)
Solovay-Strassen Implementación de la prueba de primalidad de Solovay-Strassen en Maple

Datos: Q2296113

[1] Robert Solovay; Volker Strassen (1977). «A Fast Monte-Carlo Test for Primality». SIAM J. Comput 6: 84-85.

[2] Artjuhov, M. M. (1966–1967), «Certain criteria for primality of numbers connected with the little Fermat theorem», Acta Arithmetica 12: 355-364, MR 0213289 .

[3] Borges Hernández, Cruz Enrique (2005). Test de primalidad, el AKS (Tesis). Universidad de La Laguna. Consultado el 12 de agosto de 2015.

[4] Stinson, p. 186

[5] PlanetMath

[6] Koblitz, p.129

[7] R. Motwani; P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. pp. 417-423. ISBN 978-0-521-47465-8.

[8] Pocklington test on Mathworld

[9] P. Erdős; C. Pomerance (1986). «On the number of false witnesses for a composite number». Mathematics of Computation 46 (173): 259-279. JSTOR 2008231. doi:10.2307/2008231.

[10] I. Damgård; P. Landrock; C. Pomerance (1993). «Average case error estimates for the strong probable prime test». Mathematics of Computation 61 (203): 177-194. JSTOR 2152945. doi:10.2307/2152945.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]