Criptografía (XLV): ¿Sabías que...? (IX)

Quizá la aplicación práctica más "palpable" de los números primos se dé actualmente en la criptografía, ya que en ellos descansa en gran medida el secreto de nuestras más preciadas comunicaciones en Internet.

Así, los números primos son la base del algoritmo RSA, posiblemente el criptosistema de clave pública más utilizado en la actualidad, en el cuál el par de claves (pública y privada) correspondiente a cada usuario se calcula a partir de dos números primos aleatorios lo suficientemente grandes.

La fortaleza de este algoritmo reside en el elevado coste computacional de hallar los dos factores primos de un número lo suficientemente grande resultado del producto de ambos, aunque este último sea público y, por tanto, pueda ser conocido por cualquiera, ya que esta tarea no es factible en un tiempo razonable con los algoritmos de factorización conocidos que se pueden implementar hasta la fecha y con la potencia de cálculo de los ordenadores actuales, por mucha de esta última de la que se disponga. Por tanto, esos números primos son fundamentales para salvaguardar la confidencialidad de nuestras comunicaciones en Internet y deben mantenerse en secreto, ya que su conocimiento por parte de terceras personas haría inútil cualquier esfuerzo al respecto.

Sin embargo, pese a esa "palpable" aplicación práctica en la criptografía que comentaba al principio, ni siquiera somos conscientes de que utilizamos todo esto en nuestra vida cotidiana en nuestras relaciones por Internet con las administraciones públicas, entidades bancarias, etc.

Ya he escrito en este blog diferentes entradas sobre el algoritmo RSA (ver primer post) y aquí me centraré en los aspectos básicos de los números primos que a mí me parecen más curiosos y de éstos aplicados a la criptografía.

Dicho ésto, a todos nos enseñaron en el colegio que los números primos son aquellos números naturales mayores que 1 que únicamente son divisibles por sí mismos y por la unidad, y que los números compuestos, en contraposición a éstos, son aquellos números naturales que tienen otro u otros divisores diferentes además de sí mismos y de 1, pero, al menos que yo recuerde, sin darnos mayores explicaciones ni de su historia, ni de para qué sirven.

1.- ¿Es el 1 un número primo o compuesto?:

Pues parece ser que ni una cosa ni otra, pero sólo por convención y de forma relativamente reciente, es decir y en mi opinión, porque "estorba que sea una cosa u otra" :), ya que si fuera primo o compuesto habría que volver a formular importantes teoremas dando explicaciones adicionales.

2.- ¿Desde cuando se conoce la existencia de los números primos?:

No se sabe con certeza, ya que hay quien afirma que este conocimiento podría remontarse bastantes miles de años atrás, pero sí se puede datar con seguridad, como mínimo, alrededor del año 300 a.C.

Así, Euclides define en esa época los números primos y, poco más tarde, Eratóstenes idea un método para hallar todos los números primos menores o iguales que un número dado.

Por tanto, al menos, hace ya más de 2.000 años que los matemáticos vienen estudiando los números primos. Quizá les fascinaron porque, tal y como se dice, son los "átomos" de los que están constituidos todos los números naturales, es decir, cualquier número natural se puede descomponer en un producto de factores primos.

La criba de Eratóstenes para hallar todos los números primos menores o iguales que uno dado consistía en lo siguiente:

1.- Se escriben en forma de tabla todos los números naturales hasta aquel del que queremos hallar todos los números primos menores o iguales que él, incluido este último.

2.- Se tacha el 1, porque como ya he dicho no es un número primo.

3.- Se va hasta el siguiente número no tachado y, si el cuadrado de éste no es mayor que el número del que queremos hallar todos los números primos menores o iguales que él, este número es declarado como primo y se tachan todos los números de la tabla que sean múltiplo de él, y se vuelve a repetir este paso 3.

4.- Cuando el cuadrado del siguiente número no tachado sea mayor que el número del que queremos hallar todos los números primos menores o iguales que él, se declaran como primos todos los números no tachados de la tabla.

Ejemplo: supongamos que queremos obtener todos los números primos menores o iguales a 100.

Gráficamente:

Creo que el algoritmo podría ser, más o menos, el siguiente:

En nuestro caso:

3.- ¿Cuántos números primos hay?:

Euclides fue el primero en formular una demostración sobre la infinitud de los números primos: "El conjunto formado por los números primos es infinito".

4.- ¿Es "fácil" determinar si un número dado es primo o compuesto?:

A la condición de que un número sea primo se le denomina primalidad y, por tanto, a la cuestión de determinar si un número dado es primo o compuesto se le conoce como el problema de la primalidad.

Así, a primera vista, éste parece un problema "fácil" (más que a "fácil" la pregunta debería hacer referencia a poco costoso) y basándonos en la criba de Eratóstenes podríamos probar a dividir el número impar en cuestión (evidentemente éste debe ser impar, ya que el único número primo par es el 2) entre todos los números enteros impares positivos comprendidos entre el 3 y el entero más próximo por defecto a la raíz cuadrada del número dado, pero esto es claramente inaceptable cuando el número en cuestión es lo suficientemente grande.

Una vez que desechamos este método, la siguiente "tentación" que podemos tener para dar respuesta a esta pregunta es pensar en factorizar dicho número con métodos más modernos, pero, tal y como he comentado al principio de este post, ésto, de momento, tampoco es posible en un tiempo razonable para números lo suficientemente grandes, como es el caso de RSA.

¿Es ésto importante?. Pues sí, ya que conviene recodar que RSA, el criptosistema de clave pública más utilizado en la actualidad, se basa precisamente en seleccionar aleatoriamente dos números primos grandes (cada uno de ellos del orden de 200 dígitos decimales) para generar el par de claves para cada usuario (pública y privada).

Entonces: ¿cómo se hace en la práctica para seleccionar dos números primos grandes?. Afortunadamente, existen algoritmos probabilísticos, mucho más eficientes que los de factorización, que nos pueden decir con un alto grado de confianza si un número dado es primo o compuesto, ésto es lo que se conoce como tests de primalidad, es decir, se trata de algoritmos no deterministas (no hay certeza matemática del resultado obtenido) que intentan verificar la hipótesis de que un determinado número es compuesto y si no lo consiguen aceptan que es primo con un cierto nivel de confianza.

En un post posterior, para no hacer éste excesivamente largo, compartiré lo que que voy aprendiendo sobre los tests de primalidad y pondré algunos ejemplos.  

5.- ¿Existen diferentes tipos de números primos?:

Hay multitud de clases o tipos de números primos, es decir, de subconjuntos del conjunto de números primos formados por aquellos que comparten unas determinadas características y que reciben un nombre colectivo para identificarlos. Así, entre muchas otras clases, nos encontramos, por ejemplo, con los números primos: pitagóricos, de Wieferich, etc., pero quizá los tipos de números primos con mayor aplicación en la criptografía son los primos fuertes y los primos seguros.

También, como en el caso anterior, en un post posterior compartiré lo que voy aprendiendo sobre los tipos de números primos con aplicación en la criptografía,