Números primos

El conjunto de los números primos es un subconjunto propio de los números naturales que engloba a todos los elementos de este conjunto mayores que 1 que son divisibles únicamente por sí mismos y por la unidad.

Los números primos menores que cien son 25, a saber: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97.

Existen infinitos números primos. Euclides realizó la primera demostración alrededor del año 300 a. C. :

Se demuestra su teorema utilizando reducción al absurdo:

Supongamos que hay un número finito de números primos. Si consideramos el producto de todos ellos y le sumamos uno, al dividir este nuevo número por cada uno de los primos obtenemos de resto uno. Por tanto debe de ser también primo o divisible por un primo que no aparecía en la lista inicial. Llegamos a una contradicción, y por tanto el número de primos ha de ser infinito.


¿por que son útiles los números primos?

Ahora mismo se me ocurre una muy interesante: La criptografía.

La criptografía asimétrica es el método criptográfico que usa un par de claves para el envío de mensajes. Las dos claves pertenecen a la misma persona a la que se ha enviado el mensaje. Una clave es pública y se puede entregar a cualquier persona, la otra clave es privada y el propietario debe guardarla de modo que nadie tenga acceso a ella. El remitente usa la clave pública del destinatario para cifrar el mensaje, y una vez cifrado, sólo la clave privada del destinatario podrá descifrar este mensaje.

Una función de un solo sentido es aquella cuya computación es fácil, mientras que su inversión resulta extremadamente difícil. Por ejemplo, es fácil multiplicar dos números primos juntos para obtener uno compuesto, pero es difícil factorizar uno compuesto en sus componentes primos. Una función-trampa de un sentido es algo parecido, pero tiene una "trampa". Esto quiere decir que si se conociera alguna pieza de la información, sería fácil computar el inverso. Por ejemplo, si tenemos un número compuesto por dos factores primos y conocemos uno de los factores, es fácil computar el segundo.

Cuando decimos que no es fácil factorizar es porque los números primos que se utilizan son de muchas cifras unas 200 cifras.

Me gustó, al respecto, una película que se llamaba Sneakers. Se basaba en que un matemático ruso - claro - había descubierto una manera de que la función, esta de factorizar el producto de dos primos, la resolvía muy rápido, es decir dejaba de ser función trampa y podía decodificar los mensajes a la misma velocidad que se codificaban, con lo que podía obtener los mensajes, descifrarlos, modificarlos, cifrarlos y volverlos a lanzar. Cogía los mensajes a los bancos y en vez de que la transacción fuese a Pepito iba a Juanito y la liaba parda.