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 número entero a ,

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

¿Dónde 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)}$

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

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

es válido para varios valores de la "base" a , dado que a es primo relativo de n . Si n es primo, entonces esta congruencia es cierta para todo a . Entonces, si elegimos valores de a al azar y probamos la congruencia, tan pronto como encontremos un 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 llama testigo de Euler para n ; es un testigo de la composición de n . La base a se llama mentirosa de Euler para n si la congruencia es verdadera mientras n es compuesta.

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

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

son testigos (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 hay n compuestos (impares) sin muchos testigos, a diferencia del caso de los números de Carmichael para la prueba de Fermat.

Ejemplo

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

Seleccionamos aleatoriamente un 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:

• 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 que, o 221 es primo, o 47 es un mentiroso de Euler para 221. Probamos con 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 tanto, 2 es un testigo de Euler de la composición de 221, y 47 era de hecho un mentiroso de Euler. Tenga en cuenta que esto no nos dice nada acerca de 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 sea primorepetir  k veces: elija aleatoriamente en el rango [2, n − 1] si x  = 0 o luego devuelva un rendimiento compuesto probablemente 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 la entrada n es realmente prima, entonces la salida siempre será probablemente prima . Sin embargo, si la entrada n es compuesta, entonces es posible que la salida sea incorrectamente prima . El número n se llama 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 probar esto de la siguiente manera: sean { _{a 1 , a 2 , ..., am} } _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 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 todo a con mcd( a , n ) = 1 es un testigo de Euler.

Por lo tanto, la probabilidad de falla es como máximo 2 ^{− k} (compárese con la probabilidad de falla para 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 de k suficientemente grande , 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, una prueba como ECPP o la prueba de primalidad de Pocklington ^{[ 3]} debe usarse lo que demuestra la primalidad.

Comportamiento de caso promedio

El límite 1/2 en la probabilidad de error de una sola ronda de la prueba de Solovay-Strassen es válido para cualquier entrada n , pero aquellos números n para los cuales 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, aplicada 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 COMPUESTO se encuentra en la clase de complejidad RP . ^[6]

Referencias

1. Artjuhov, MM (1966-1967), "Ciertos criterios para la primalidad de los números relacionados con el pequeño teorema de Fermat", Acta Arithmetica , 12 : 355–364, MR  0213289
2. El criterio de Euler
3. Prueba de Pocklington en Mathworld
4. P. Erdős; C. Pomerancia (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. Pomerancia (1993). "Estimaciones de error de caso promedio para la prueba principal probable fuerte". Matemáticas de la Computación . 61 (203): 177-194. doi :10.2307/2152945. JSTOR  2152945.
6. R.Motwani; P. Raghavan (1995). Algoritmos aleatorios . Prensa de la Universidad de Cambridge. págs. 417–423. ISBN 978-0-521-47465-8.

Otras lecturas

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

enlaces externos

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