------------------------------------------
Generación y comprobación de primos con openssl
26 may 2023
------------------------------------------
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 trivial 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, el que tiene la forma
6611*2^6611+1 y consta de 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".
