¿Cómo sabemos que un número es primo?. Para determinar si un número es primo se realizan distintas pruebas deterministas, por ejemplo la factorización , aunque a veces se sustituyen por probabilísticas que generan números casiprimos / seudoprimos. En la actualidad la mayoría de las pruebas se efectúan con medios computacionales donde se introducen los conceptos de medidas de tiempo y complejidad, importantes para analizar la fortaleza de los algoritmos con independencia de la potencia de la máquina.
A partir de mediados del siglo XX la importancia de identificar números primos comienza a ser imprescindible, hasta ese momento no tenían relevancia, salvo en el entorno matemático, pero esto cambia. En la actualidad quien sea capaz de operar con estos números de forma rápida tiene la llave del reino, la mayoría de las transacciones económicas, sistemas de comunicación y otras muchas cosas dependen de estos números, de su multiplicación y factorización.
En 1.974 Ralph C. Merkle propone un proyecto a Lance Hoffman en la universidad de Berkeley y este lo rechaza. Eran los cimientos de la criptografía de clave pública, qué despiste de Hoffman.
En 1.976 Whitfield Diffie y Martin Hellman publican la idea de disponer de distintas claves para cifrar y descifrar mensajes, haciendo que una parte de la clave sea pública. En 1.977 Ronald Rivest, Adi Shamir y Leonard Adleman sugieren que los números primos grandes podrían utilizarse para cifrar mensajes, surge el algoritmo RSA. Lo plantean de la siguiente forma:
La multiplicación de dos números es fácil para los computadores, pero el proceso inverso, es decir la obtención de los números a partir del producto es difícil y mucho más si tomamos primos.
A partir de los conceptos de Diffie – Hellman – Merkle (criptografía de clave pública) y del algoritmo Rivest – Shamir – Adleman, surge la tremenda importancia de conocer si un número es primo y la necesidad de tener pruebas rápidas de identificación. Esta situación ha desencadenado una carrera para la obtención de métodos y técnicas que los provean, tanto para cifrar los mensajes como para descifralos. Los “buenos” los ciframos para que los “malos” no los vean.
Como entre buenos y malos anda el juego, hacemos una incursión en las suposiciones, Bobby Inman (NSA) afirmó que la criptografía de clave pública la habían descubierto a mediados de la década de 1.960. En 1.970 James Ellis (SS Británico – GCHQ) dice disponer de ello, otros apuntan que fue su continuador Clifford Cocks en 1.973 quien dio con ello. Es lo de siempre, los enemigos son los malos, los otros los buenos y en medio los ciudadanos, sin enterarnos de nada.
¿Cómo generan números primos?.
- Generar un número aleatorio p de n bits.
- Poner a uno el bit más significativo (así garantizamos que el número es de n bits) y el menos significativo (debe ser impar para poder ser primo)
- Intentar dividir p por una tabla de primos precalculados (usualmente aquellos que sean menores que 2000). Esto elimina gran cantidad de números no primos de una forma muy rápida. Baste decir a título informativo que más del 99.8 % de los números impares no primos es divisible por algún número primo menor que 2000.
- Ejecutar tests de primalidad sobre p para ver si es primo hasta el grado de certeza deseado
- Si el test falla, incrementar p en dos unidades y volver al paso 3.