Ésta es la entrada 91 de este blog. Decidí dedicarla a los números primos porque 91 es uno de los números del 0 al 100 que fácilmente puede pensarse que es primo, sin que lo sea. Todos los números de dos cifras que terminan en 1, o son primos o son fácilmente identificables como múltiplos de 3, excepto el 91.

Los múltiplos de 3 son muy fáciles de distinguir, porque la suma de sus cifras es 3, 6, 9.

Veamos los números menores a 100 terminados en 1:

11, 21, 31, 41, 51, 61, 71, 81, 91

Las cifras de 21, 51 y 81 suman 3, 6 y 9 respectivamente, por lo que son múltiplos de 3 y, por tanto, no son primos.

11, 31, 41, 61 y 71 son primos.

¡El 91 no! y no es tan fácil de identificar, pues es el producto de 7 x 13. La tabla del 7 suele aprenderse hasta el 7×10 o 7×12 (aunque en algunas escuelas la aprenden hasta el 15 o 20). Por lo mismo, los múltiplos de 13 no son tan familiares para los estudiantes.

Al identificar esa peculiaridad del 91, se me ocurrió dedicar una entrada sólo a los números primos, algunas de sus características, algunas formas de encontrarlos y cómo se usan para encriptar mensajes, cuestión que no había logrado entender hasta que me propuse comprenderlo para compartirlo aquí. Espero que les parezca tan interesante como me lo pareció a mí.
Empecemos por el principio.

Los números, por sus características, pueden clasificarse de diferentes formas. Entre los números naturales (1, 2, 3…) una clasificación muy sencilla es: pares (pueden dividirse entre dos sin que quede residuo) e impares (no pueden dividirse entre dos sin que quede residuo).

Otra clasificación mucho menos sencilla, pero muy importante, es la que separa los números naturales (enteros positivos) en números primos, compuestos y el número 1.

Los números primos son aquellos que sólo tienen dos divisores, es decir, sólo pueden dividirse, sin dejar residuo, entre sí mismos y entre 1.

Los números compuestos son aquellos que tienen más de dos divisores.

El uno sólo tiene un divisor, por lo que no se considera ni primo ni compuesto.

Muchos matemáticos consideran a los números primos los “átomos” de las matemáticas, pues con ellos se forman todos los números compuestos.

Formas de encontrarlos:

Para establecer si un número es primo, se puede usar un procedimiento que se basa en la definición: se toma el número y se va dividiendo entre todos los números entre uno y dicho número. Si las únicas divisiones que dan enteras son entre uno y entre el número original, hemos encontrado un número primo.

Es un método seguro, pero muy lento. Podemos abreviarlo si calculamos la raíz cuadrada del número. Si tiene una raíz cuadrada entera, no es primo. Si no es entera, entonces lo dividimos sólo entre los primos menores a dicha raíz cuadrada.

Por ejemplo, para saber si 91 es primo, se obtiene su raíz cuadrada, 9.53. Como no es entera, se divide 91 entre 2, 3, 5, 7, que son los únicos primos menores a 9. Al llegar a 91 / 7 obtenemos 13, que es entero y, por tanto, nos enteramos de que 91 no es primo.

También se pueden buscar formas de acomodar 91 puntos en forma de rectángulo. Sí es posible, se obtiene un rectángulo de 7 filas por 13 columnas o uno de 13 filas por 7 columnas. Entonces no es primo. 11 puntos en cambio sólo pueden acomodarse en una fila de 11 puntos u 11 filas de un punto, por lo que 11 es primo.

Otro método es la criba de Eratóstenes, en la cual se van tachando todos los múltiplos de cada primo que se encuentre. Es muy práctica para números pequeños. Había escrito sobre este proceso aquí.

También hay algunas fórmulas que permiten encontrar números primos como la que veremos en la siguiente sección.

Unos primos especiales, los primos de Mersenne

Los primos de Mersenne tienen la siguiente forma de calcularse:

2^p -1, donde p también es un número primo.

Nota, no todos los primos sustituidos en la p de la fórmula generan un nuevo primo.

Veamos algunos que sí:

Para p = 2
2^2 – 1 = 4 – 1 = 3

Para p = 3
2^3 – 1 = 8 – 1 = 7

Para p = 5
2^5 – 1 = 32 – 1 = 31

Para p = 7
2^7 – 1 = 128 – 1 = 127

Sin embargo, para p = 11 ya no se cumple, pues 2 ^11 – 1 = 2047 no es primo, es el resultado de 23 x 89.

Tengo entendido que se conocen sólo 51 primos de Mersenne.

Algo simpático con respecto a estos números, es que están directamente relacionados con los números perfectos, aquellos cuya suma de factores menores a sí mismo (factores propios) es igual a dicho número. También se conocen solamente 51 números perfectos, los cuales se obtienen mediante la fórmula:

2^ (p-1)*(2^p-1)

En la que, nuevamente, p es primo. Tengo entendido que sólo funcionan para los mismos p que los primos de Mersenne.

Para p = 2
2 ^ ( 2 – 1) * ( 2^2 – 1 ) = 2 * (4 – 1) = 6

Los factores propios del 6 son 1, 2, 3, que suman dan 6.

Para p = 3
2 ^ ( 3 – 1) * ( 2^3 – 1 ) = 4 * (8 – 1) = 28

Los factores propios del 28 son 1, 2, 4, 7, 14, que suman 28

Para p = 5
2 ^ ( 5 – 1) * ( 2^5 – 1 ) = 16 * (31) = 496

Los factores propios del 496 son 1, 2, 4, 8, 16, 31, 62, 124, 248, que suman 496.

(Ver más sobre números perfectos aquí).

Por cuestiones de espacio no pondremos más fórmulas para encontrar primos en esta entrada, pero agradeceré que compartan los procedimientos o fórmulas que conozcan en los comentarios.

Algunas curiosidades con respecto a los números primos:

El 2 es el único primo par, pues todos los demás pares son sus múltiplos.

El 2 y el 3 son los únicos primos consecutivos, pues entre cada par de todos los demás números consecutivos siempre habrá uno que sea par y, por tanto, no sea primo.

El 5 y el 7 son primos gemelos, por haber sólo un número entre ellos. Los siguientes son los pares de primos gemelos menores a 100. Por lo que se ve, 3, 5, 7 serían los únicos 3 primos “consecutivos” con una diferencia de 2 entre cada par. Desconozco cómo se les llama y desconozco si hay otro caso entre números más grandes. Si ustedes lo conocen, compártanlo en los comentarios, por favor.

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)

Se sabe que hay una cantidad infinita de números primos, se desconoce cuántos pares de primos gemelos existen.

¿Para qué sirven los números primos?

Todo lo que tenga relación con multiplicar y con dividir puede facilitarse mediante los números primos.

Si vamos a multiplicar, por ejemplo, 14 x 15 podemos descomponerlos en sus factores primos y realizar la multiplicación de una forma que nos convenga más, aprovechando que el orden de los factores no altera el producto:

14 x 15 = 2 x 7 x 3 x 5 = 2 x 5 x 3 x 7 = 10 x 21 = 210

Lo mismo para dividir, por ejemplo, 210 entre 15, podemos optar por dividir ambos entre su factor primo 3, obteniendo 70 entre 5, que es más rápido de calcular: 14.

Para trabajar con fracciones son indispensables los factores primos, tanto para obtener el mínimo común múltiplo de los denominadores como para simplificar todas las respuestas obtenidas. (Ver más sobre fracciones aquí y aquí).

Al factorizar polinomios en álgebra, también pueden ser muy útiles los factores primos del término independiente, aunque en este caso algunos de los factores usados pueden no ser primos:

x^2 – 20 x + 91 = ( x – 13 ) ( x – 7 )

Los números primos en la criptografía

Había escuchado y leído frecuentemente que los números primos eran indispensables para encriptar mensajes de forma segura, pero no tenía claro cómo se hacía eso.

Después de una semana de leer libros y navegar por Internet, tengo una idea un poco menos borrosa del tema. Trataré de transmitirlo aquí de forma simple.

Como introducción, mencionaré que existen métodos de encriptar que son simétricos, es decir, se usa un procedimiento para encriptar y el mismo procedimiento, pero al revés, para desencriptar.

Un ejemplo muy sencillo (a veces llamado “alfabeto doblado”) sería intercambiar las letras del alfabeto. En vez de A se escribe Z, en vez de B, Y; y así sucesivamente.

A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z ->
Z Y X W U V T S R Q P O Ñ N M L K J I H G F E D C B A

Como nuestro alfabeto tiene 27 letras, la letra central, N, no cambiaría

“NUEVE” se encriptaría como “NEUFU” y se desencriptaría como “NUEVE” usando la misma clave, invertida. Al «doblar» el alfabeto, z y a se corresponden de ida y vuelta, por lo que el procedimiento al desencriptar es básicamente el mismo que al encriptar.

Ver más sobre reversibilidad aquí.

Criptografía asimétrica de clave pública y clave privada

El algoritmo RSA (iniciales de sus creadores Rivest, Shamir y Adleman) es un algoritmo asimétrico, es decir, no se usa el mismo procedimiento, aunque invertido, para encriptar y desencriptar.

Su seguridad se basa, además de en ser asimétrico, en la dificultad para factorizar números grandes, aún con supercomputadoras.

Para encriptar se usa una clave pública, que no se oculta al público en general, y para desencriptar se usa una clave privada, que sólo quien desencriptará conoce, y que está basada en los factores primos de uno de los números de la clave pública.

Por ejemplo, el 91 puede servir para formar la clave pública y el 7 y el 13 servirían para formar la clave privada. Sólo que ya con esos números, así de pequeños como los ven, el proceso matemático implica números de alrededor de 50 cifras, que una calculadora normal no puede manejar, así que veremos un ejemplo con números mucho más pequeños.

De hecho, mientras más aumenta la capacidad de cómputo de la humanidad, más grande se requiere que sean los números primos a usar. El proceso completo es, como podría esperarse, muy complejo. La información se cifra por bloques y debe haber una serie de candados que hagan que todo funcione bien, empezando por usar primos de muchísimas cifras (más de 100, incluso más de 500).

En nuestro ejemplo usaremos dos números primos muy pequeñitos, que sí pasan los primeros candados.

Estos son los números primos:

p = 3, q = 11

La multiplicación de esos primos, es una parte de la clave pública:

n = 33

Para tener la otra parte de la clave pública, y la clave privada, se necesita primero calcular un número que se llama fi o indicador de Euler, y que se obtiene multiplicando los primos anteriores disminuidos en 1:

fi = (p-1) (q-1) = (2) (10) = 20

Ahora se busca un número e mayor o igual a 3 y menor a fi – 2 que sea co-primo con fi, es decir, que sean primos entre sí, porque el máximo común divisor de ambos sea 1.

Para elegir ese número, debe tomarse en cuenta también que, al dividir fi+1 entre e, se obtiene un entero d, que forma parte de la clave privada.

d x e exceden exactamente en 1 a fi. Por ello escogí para e el 3, porque 3 x 7 = 21, que es uno más que 20.

e también forma parte de la clave pública. En nuestro caso:

e = 3

d forma parte de la clave privada. En nuestro caso:

d = 7

Listo, la clave pública está formada por el 3 y el 33 y la clave privada está formada por el 7 y el mismo 33.

Descomponiendo el 33 en sus factores primos es muy sencillo dar con el 7, pero descomponer los números que usan los bancos para encriptar es materialmente imposible de lograr con los recursos computacionales actuales, por lo que sólo quien conozca los factores primos con los que se formó la clave pública podrá formar la clave privada.

Veamos cómo encriptar el número 9. (ver más sobre por qué me gusta tanto el 9 aquí)

y será el número encriptado y se obtiene de elevar 9 (el número a encriptar) a la 3, que forma parte de la clave pública, dividiéndolo entre 33, la otra parte de la clave pública, y obteniendo el resto. El resto, 3, es 9 encriptado con esta clave.

y = 9^3 mod 33 = 3

9^3 = 729, 729 / 33 = 22 y sobran 3

z será el número desencriptado. No vamos a hacer el proceso anterior en reversa, por eso es un proceso asimétrico. Lo vamos a hacer en el mismo sentido, pero usando la clave privada. Se obtiene elevando 3, (el número encriptado) a la 7, que forma parte de la clave privada, dividiéndolo entre el mismo 33 anterior, y obteniendo el resto. El resto, 9 es en número desencriptado:

z = 3^7 mod 33 = 9

3^7 = 2187, 2187 / 33 = 66 y sobran 9

Entonces, si quiero decirle a alguien en secreto que quiero 9 brownies, encripto el dato como acabo de explicar y obtengo un 3, que le envío a la persona para que lo desencripte y obtenga, nuevamente, un 9, como también acabo de explicar.

Obviamente la mayoría de los mensajes encriptados que se envían son mucho más largos y delicados, lo que amerita su encriptación.

Las matemáticas que se usan para justificar que esto funciona en general y los candados que se requieren para asegurar que funcione en lo particular (no todas las combinaciones de primos funcionan bien, según pude observar) quedan fuera del alcance de este blog.

Sólo quiero agregar una información que quizá se estén preguntando, como yo lo hice mientras indagaba todo esto:

Factorizar un número grande con los procedimientos habituales (los descritos aquí y algunos más optimizados) puede ser extremadamente tardado. Sin embargo, si ya se tiene una lista de los números primos menores a él, ¿nos podríamos limitar a probar las combinaciones más prometedoras entre ellos y encontrar los factores muy rápido?

En teoría sí. Pero si se usan dos números primos de, digamos, 100 cifras, la multiplicación de ellos dará un número de ¡200 cifras!

Hay más de 455 millones de números primos de 10 cifras… imagínense los que habrá de 200 cifras.

Es inmanejable para la capacidad de cómputo y el conocimiento matemático actual.
Si se da un brinco sustancial en alguno de esos dos aspectos, la seguridad de nuestras transacciones digitales se vería seriamente amenazada. Supongo que se inventaría algo aún más sofisticado, pero eso queda muy, pero muy lejos del alcance de este blog.

Para cerrar

Entender, aunque fuera superficialmente, el método de encriptación usando números primos era un reto personal que, al superarlo, quise compartir con ustedes.

Después de la ardua indagación buscando entender este procedimiento, reflexioné que, de alguna manera, el que no todos tengamos conocimientos profundos en matemáticas ayuda para que este algoritmo sea seguro y, con él, nuestras transacciones y comunicaciones. Por esa misma razón, tener sólidos conocimientos de matemáticas nos da algunas ventajas sobre quienes no los tienen.

Por ejemplo, hace unos días en una papelería, me disponía a realizar una compra de varios productos. Lo que ya tenía en el carro de las compras sumaba 1700 pesos y me interesaba comprar un producto que costaba 1300 pesos, aunque al lado, en la vitrina, había uno que cumplía el mismo objetivo, pero costaba 2300 pesos, obviamente por ser mucho más completo.

Entonces caí en cuenta de algo sobre la política de descuentos de la tienda ese día:

Si yo compraba productos por $3000 pesos, me harían un 20% de descuento, por lo que pagaría $2400 pesos en total.

Si yo compraba productos por $4000 pesos, me harían un 40% de descuento, por lo que pagaría $2400 pesos en total.

Es decir, tanto si le sumaba a lo que llevaba en el carro el producto de $1300 como si le sumaba el de $2300, al final pagaría lo mismo, $2400.

Obviamente compré el de $2300. De algo debe servirme el que me gusten las matemáticas ¿no creen?.

Espero que ustedes poco a poco vayan sintiéndose más cómodos con los números y puedan aprovechar oportunidades como esa en su día a día.

Como siempre, gracias por leer, comentar y compartir.

¡Hasta el siguiente miércoles!

Rebeca

PD1: Aún no he logrado insertar en esta sección un botón que permita seguir el blog… lamento la molestia que implica ir a la página principal para hacerlo.

PD2: Quiero agradecer a estas páginas en las que me apoyo constantemente para redactar el blog: pixabay y webresizer

PD3: Entendí lo que compartí aquí principalmente leyendo wikipedia y observando algunos videos de Derivando y en especial, este video de Alex Narvaez