Prueba de primalidad de 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 primalidad de Miller-Rabin , pero tiene una gran importancia histórica al mostrar la viabilidad práctica del criptosistema RSA . La prueba de Solovay-Strassen es esencialmente una prueba de primos probables de Euler-Jacobi .

Conceptos

Euler demostró ^[2] que para cualquier número primo impar p y cualquier entero a ,

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

donde es 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 entero impar. El símbolo de Jacobi se puede calcular en 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)}$

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

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

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

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

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

Ejemplo

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

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

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

Esto da como resultado que 221 es primo o 47 es un mentiroso de Euler para 221. Probamos otro a aleatorio , esta vez eligiendo a  = 2:

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

Por lo tanto, 2 es un testigo de Euler para la composición de 221, y 47 era, de hecho, un mentiroso de Euler. Obsérvese que esto no nos dice nada sobre los factores primos de 221, que en realidad son 13 y 17.

Algoritmo y tiempo de ejecución

El algoritmo se puede escribir en pseudocódigo de la siguiente manera:

entradas : n , un valor para probar la primalidad k , un parámetro que determina la precisión de la prueba salida : compuesto si n es compuesto, de lo contrario probablemente primorepetir  k veces: Elija un número aleatorio en el rango [2, n − 1] si x  = 0 o entonces devuelva compuesto , probablemente devuelva primo ${\displaystyle x\gets \left({\tfrac {a}{n}}\right)}$     ${\displaystyle a^{(n-1)/2}\not \equiv x{\pmod {n}}}$    

Usando algoritmos rápidos para exponenciación modular , el tiempo de ejecución de este algoritmo es O( k ·log ³ n ), donde k es el número de valores diferentes de a que probamos.

Precisión de la prueba

Es posible que el algoritmo devuelva una respuesta incorrecta. Si el valor de entrada n es, en efecto, primo, entonces el resultado siempre será, correctamente, probablemente primo . Sin embargo, si el valor de entrada n es compuesto, entonces es posible que el resultado sea incorrectamente probablemente primo . El número n se denomina entonces pseudoprimo de Euler-Jacobi .

Cuando n es impar y compuesto, al menos la mitad de todos los a con mcd( a , n ) = 1 son testigos de Euler. Podemos demostrarlo 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),}$

Ahora sabemos que

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

Esto da como resultado que cada a _i da un número a · a _i , que también es un testigo de Euler. Por lo tanto, cada mentiroso de Euler da un testigo de Euler y, por lo tanto, el número de testigos de Euler es mayor o igual que el 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 esto con la probabilidad de fallo de la prueba de primalidad de Miller-Rabin , que es como máximo 4 ^{− k} ).

Para fines de criptografía, cuantas más bases a probemos, es decir, si elegimos un valor suficientemente grande de k , mejor será la precisión de la prueba. Por lo tanto, la probabilidad 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 ECPP o la prueba de primalidad de Pocklington ^{[3] que} prueba la primalidad.

Comportamiento de caso promedio

El límite 1/2 de la probabilidad de error de una sola ronda de la prueba de Solovay–Strassen se cumple para cualquier entrada n , pero aquellos 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: 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 aleatorio . ^{[4] [5]} 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.

Complejidad

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

Referencias

1. Artjuhov, MM (1966–1967), "Ciertos criterios de primalidad de números relacionados con el pequeño teorema de Fermat", Acta Arithmetica , 12 : 355–364, MR  0213289
2. Criterio de Euler
3. Prueba de Pocklington en Mathworld
4. P. Erdős; C. Pomerance (1986). "Sobre el número de testigos falsos para un número compuesto". Matemáticas de la computación . 46 (173): 259–279. doi :10.2307/2008231. JSTOR  2008231.
5. I. Damgård; P. Landrock; C. Pomerance (1993). "Estimaciones de error de caso promedio para la prueba de primos probables fuertes". Matemáticas de la computación . 61 (203): 177–194. doi :10.2307/2152945. JSTOR  2152945.
6. R. Motwani; P. Raghavan (1995). Algoritmos aleatorios . Cambridge University Press. págs. 417–423. ISBN 978-0-521-47465-8.

Lectura adicional

• Solovay, Robert M.; Strassen, Volker (1977). "Una prueba rápida de Montecarlo para primalidad". Revista SIAM de Computación . 6 (1): 84–85. doi :10.1137/0206006.Véase también Solovay, Robert M.; Strassen, Volker (1978). "Fe de erratas: una prueba rápida de Montecarlo para primalidad". SIAM Journal on Computing . 7 (1): 118. doi :10.1137/0207009.
• Dietzfelbinger, Martin (29 de junio de 2004). "Pruebas de primalidad en tiempo polinomial, desde algoritmos aleatorios hasta "PRIMES está en P"". Apuntes de clases sobre informática . Vol. 3000. Springer. ISBN 978-3-540-40344-9.

Enlaces externos

• Implementación de la prueba de primalidad de Solovay-Strassen en Maple