Test de Solovay-Strassen

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

${\displaystyle 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

${\displaystyle 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 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$.[5] Por ejemplo, para ${\displaystyle n=65}$, el conjunto de mentirosos de Euler tiene orden 8 y ${\displaystyle =\{1,8,14,18,47,51,57,64\}}$, y ${\displaystyle (\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:

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle n=p_{1}^{\alpha _{1}}\ldots p_{t}^{\alpha _{t}}}$. Se define en este caso:

${\displaystyle \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 ${\displaystyle \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) ${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)}$ si ${\displaystyle a\equiv b{\pmod {p}}}$

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

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

(IV) ${\displaystyle \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.}$

Como se acaba de mencionar, si p es primo impar entonces

${\displaystyle \left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}}$ para todo ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \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.

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
• ${\displaystyle ({\tfrac {a}{n}})}$ mod n  =  ${\displaystyle ({\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.
• ${\displaystyle ({\tfrac {a}{n}})}$ mod n  =  ${\displaystyle ({\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.

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

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:

${\displaystyle (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:

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

y entonces se sabe que

${\displaystyle (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.

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

${\displaystyle 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.

• 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