A la búsqueda de números primos

Hasta anteayer las pruebas para determinar si un número de 100 cifras era primo habrían durado un siglo, incluso con la ayuda de un computador. Hoy basta con un minuto.

Los números primos son unidades con las que se forman, por multiplicación, todos los demás. Si un número es primo, entonces no existen números naturales menores cuyo producto sea dicho número. Por ejemplo, 11 es un número primo, ya que no se puede expresar como producto de factores menores; solo 1 x 11 es igual a 11. Por contra, si un número es compuesto, entonces se podrá expresar como producto de dos o más factores primos. Así, 12 es igual a 2 x 2 x 3. Todo número entero mayor que 1 es primo o producto de un conjunto único de números primos. Este hecho, conocido ya por los griegos de la antigüedad, es esencial para el sistema de los números naturales, hasta el punto de que se ha convenido en llamarle teorema fundamental de la aritmética.

¿Cómo determinar si cierto número es primo o compuesto? El procedimiento más directo consiste en dividir el número en cuestión por 2, 3, 4, y así sucesivamente. Si una de las divisiones es exacta (esto es, el resto de la misma es cero), entonces se tratará de un número compuesto, siendo el divisor y el cociente factores suyos. Pero si ninguna de las divisiones es exacta, para todos los números hasta el número en cuestión, nos hallaremos entonces ante un número primo. La verdad es que no se necesita llegar hasta ese número; el proceso termina en cuanto el divisor supera la raíz cuadrada del número. La razón estriba en que los factores siempre se presentan a pares; si uno de ellos es superior a la raíz cuadrada, entonces debe existir otro inferior a la misma.

La finalización de las divisiones al llegar a la raíz cuadrada hace que la prueba de primalidad sea mucho más rápida. Hay otros atajos, como el de borrar todos los números pares posteriores al 2. Sin embargo, este método de división es totalmente inviable cuando se trata de los mayores números primos que se conocen. Considérese por ejemplo el número 244.497 − 1, que tiene 13.395 cifras. Este número es primo, como lo demostraron, en 1979, Harry L. Nelson y David Slowinski, del Laboratorio Lawrence Livermore. Si un computador llevase a cabo las divisiones a razón de un millón por segundo, y si parara al llegar a la raíz cuadrada del número, emplearía 106684 años en efectuar el trabajo.

Puedes obtener el artículo en...

¿Tienes acceso a la revista?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.

Responsable: Prensa Científica, S.A. Finalidad: enviarle por correo electrónico los boletines que haya solicitado recibir. Derechos: tiene derecho a acceder, rectificar y suprimir sus datos, así como a otros derechos, como se explica en la información adicional y detallada que puede consultar en nuestra Política de Privacidad.