Comprobación y generación de primos con openssl
Buscando otra cosa (a raíz de un artículo sobre bcrypt) descubro las capacidades de openssl para tratar con primos. Interesante.
En cuanto a generar primos la cosa es tan sencilla como esta:
openssl prime -generate -safe -bits 128
339178402112628387707471048642245838243
Y ahí tenemos un primo de 128 bits. Podríamos por ejemplo generar dos primos aleatorios de 512 bits para multiplicarlos y tener una clave RSA de 1024 bits.
La opción -safe hace que el número generado n y también (n-1)/2 sean primos evitando así que la factorización del producto de dos primos así sea más fácil.
Ahora para comprobar si un número es primo basta con
openssl prime 12176482347111
B130EE7A867 (12176482347111) is not prime
instantáneamente. Vamos a ponérselo algo más difícil. Se sabe que el número de Fibonacci que ocupa el lugar 9311 es primo y tiene 1946 dígitos.
Busqué un rato si había algo hecho y fácil de usar para calcular números de Fibonacci en precisión arbitraria. Acabé haciendo un script trivial en Python que es lo suficientemente rápido para mi, de hecho tarda unas cinco centésimas de segundo en escribir el resultado.
El código es el siguiente:
#!/usr/bin/env python3
# -_- coding: utf8 -_-
n = 9311
i = 2
a= 1
b= 1
while i < n:
a, b = b, a + b
i += 1
print(b)
Y vamos a comprobar la primalidad con openssl comprobando lo que tarda.
time openssl prime $(./fibo.py)
(aquí openssl escribe el número en hexadecimal y entre paréntesis en decimal aclarando "is prime"
El tiempo es de poco más de seis segundos en un ordenador de sobremesa antiguo.
Otro primo conocido es 872! + 1 que tiene 2188 dígitos. Aquí voy a usar el programa calc, de línea de órdenes por supuesto.
time openssl prime $(calc "1+872!")
Y le lleva unos 11 segundos decidir que es primo. Curiosa la diferencia cuando tiene casi las mismas cifras que el anterior.
Por último me decidí por un primo de Cullen, que tiene 1994 dígitos decimales.
time openssl prime $(calc "6611*2^6611+1")
En este caso tarda casi 21 segundos en decidir correctamente que es primo. Por cierto que estos números de Cullen en hexadecimal están formados por unos pocos dígitos seguidos de una laaarga lista de ceros y un 1 para terminar.
openssl después de eliminar los pares excepto el dos y el tres hace una serie de divisiones de prueba (más cuanto mayor es el número) y a continuación una serie de tests probabilistícos de Miller-Rabin para decidir si el número es primo con un margen de error menor que 2^-256 para números "grandes" (>2048 bits) y menor que 2^-128 para los "pequeños".
== Referencias ==