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 primordialidad de Miller-Rabin , pero tiene una gran importancia histórica para demostrar la viabilidad práctica del criptosistema RSA . La prueba de Solovay-Strassen es esencialmente unaPrueba de pseudoprime de Euler-Jacobi .
Conceptos
Euler demostró [2] que para cualquier número primo py cualquier entero a ,
dónde 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 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 .
Dado un número impar n podemos contemplar si la congruencia
sostiene para varios valores de la "base" un , dado que una es relativamente primo a n . Si n es primo, entonces esta congruencia es verdadera para todo a . Entonces, si elegimos valores de a al azar y probamos la congruencia, tan pronto como encontremos una 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 denomina testigo de Euler para n ; es un testimonio de la composición de n . La base a se llama mentirosa de Euler para n si la congruencia es verdadera mientras que n es compuesta.
Para cada n impar compuesto , al menos la mitad de todas las bases
son testigos (de Euler) ya que el conjunto de mentirosos de Euler es un subgrupo adecuado de . [3] Por ejemplo, para, el conjunto de los mentirosos de Euler tiene orden 8 y , y tiene orden 48.
Esto contrasta con la prueba de primordialidad de Fermat , para la cual la proporción de testigos puede ser mucho menor. Por lo tanto, no hay n compuesto (impar) sin muchos testigos, a diferencia del caso de los números de Carmichael para la prueba de Fermat.
Ejemplo
Suponga que deseamos determinar si n = 221 es primo. Escribimos ( n −1) / 2 = 110.
Seleccionamos 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 , calculamos:
- a ( n −1) / 2 mod n = 47110 mode 221 = −1 mode 221
- mod n = mod 221 = −1 mod 221.
Esto da que, o bien 221 es primo, o 47 es un mentiroso Euler para 221. Tratamos otra al azar una , esta vez la elección de un = 2:
- a ( n −1) / 2 mod n = 2110 mod 221 = 30 mod 221
- mod n = mod 221 = −1 mod 221.
Por tanto, 2 es un testigo de Euler de la composición de 221, y 47 fue de hecho un mentiroso de Euler. Tenga en cuenta 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: elegir al azar en el rango [2, n - 1] si x = 0 o a continuación, volver compuesta de retorno , probablemente, primer
Usando algoritmos rápidos para exponenciación modular , el tiempo de ejecución de este algoritmo es O ( k · log 3 n ), donde k es el número de valores diferentes de a que probamos.
Exactitud de la prueba
Es posible que el algoritmo devuelva una respuesta incorrecta. Si la entrada n es prima, entonces la salida siempre será probablemente prima correcta . Sin embargo, si la entrada n es compuesta, entonces es posible que la salida sea incorrectamente probablemente prima . El número n se denomina pseudoprime 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 , ..., a m } los mentirosos de Euler y a un testigo de Euler. Entonces, para i = 1,2, ..., m :
Porque lo siguiente es válido:
ahora sabemos que
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 testimonio 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 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 esto con la probabilidad de falla para la prueba de primaria de Miller-Rabin , que es como máximo 4 - k ).
Para propósitos de criptografía, cuantas más bases a probamos, es decir, si elegimos 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 utiliza 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 [ 4] debe utilizarse, lo que demuestra la primordialidad.
Comportamiento de caso promedio
El límite 1/2 de la probabilidad de error de una sola ronda de la prueba de Solovay-Strassen es válido para cualquier entrada n , pero los 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
para k rondas de la prueba, aplicado a n ≤ x uniformemente aleatorio . [5] [6] 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 Solovay-Strassen muestra que el problema de decisión COMPOSITE se encuentra en la clase de complejidad RP . [7]
Referencias
- ^ Artjuhov, MM (1966-1967), "Ciertos criterios para la primordialidad de los números relacionados con el pequeño teorema de Fermat", Acta Arithmetica , 12 : 355-364, MR 0213289
- ^ Criterio de Euler
- ^ PlanetMath
- ^ Prueba de Pocklington en Mathworld
- ^ P. Erdős; C. Pomerance (1986). "Sobre el número de testigos falsos por un número compuesto". Matemáticas de la Computación . 46 (173): 259–279. doi : 10.2307 / 2008231 . JSTOR 2008231 .
- ^ I. Damgård; P. Landrock; C. Pomerance (1993). "Estimaciones de error de caso promedio para la prueba de prima fuerte probable". Matemáticas de la Computación . 61 (203): 177-194. doi : 10.2307 / 2152945 . JSTOR 2152945 .
- ^ 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 Monte-Carlo para la primalidad". Revista SIAM de Computación . 6 (1): 84–85. doi : 10.1137 / 0206006 . Ver también Solovay, Robert M .; Strassen, Volker (1978). "Errata: una prueba rápida de Monte-Carlo para la primalidad". Revista SIAM de Computación . 7 (1): 118. doi : 10.1137 / 0207009 .
- Dietzfelbinger, Martin (29 de junio de 2004). "Prueba de primalidad en tiempo polinomial, de algoritmos aleatorios a" PRIMES está en P " ". Apuntes de conferencias en informática . 3000 . ISBN 978-3-540-40344-9.
enlaces externos
- Solovay-Strassen Implementación de la prueba de primalidad Solovay-Strassen en Maple