miércoles, 12 de diciembre de 2007

Búsqueda de Números Primos Grandes.

Un número primo es un número que sólo es divisible por 1 y por el propio número. Por ejemplo 2, 3, 5, 7, 11, 13, 17, ... son números primos.

Euclides demostró que existen infinitos números primos allá por el 450 d. C. (Esto también lo demostraría nuestro ya nombrado Euler). Este hecho sería la mecha que encedería el deseo de encontrar entre los matemátic@s de todas partes y de todas las épocas, el número primo más grande que existe. (Interés que luego se incrementó con el desarrollo de la Criptografía).

Existe un método elemental para comprobar si un número es primo, éste consiste en ir dividiendo el número que me dan entre los sucesivos números primos menores que el número dado hasta que el cociente sea más pequeño que el divisor. Si tras esas divisiones no ha dado el resto cero el número es primo.
Por ejemplo: 37: 2 = 18 Resto 1, 37 : 3 =12 Resto 1, 37 : 5 = 7 Resto 2, 37 : 7 = 5 Resto 2. LLegamos a la conclusión que 37 es primo porque el cociente anterior dió 5.
Este método es viable para números pequeños, e incluso para números más grandes gracias a los ordenadores, pero cuando los números son muy muy grandes, este método se convierte en una locura. Lo que hizo pensar en la búsqueda de algoritmos o de fórmulas generadoras de números primos como la solución que aliviara esta búsqueda.

Hasta 1536 se pensó que los números de la forma 2^n-1 eran todos primos, pero ese año Hudalricus Regius, demostró que 2^11 - 1 = 2047 era el producto de 23 y 89. Sin embargo, muchos (se supone que infinitos) números primos cumplen esa condición. A los números primos que cumplen esa condición se les llama números primos de Mersenne. Y el uso de la fórmula 2^n - 1 es uno de los principales métodos para calcular números primos grandes.

Fermat (en 1640) creyó que había encontrado con la expresión 2^k + 1, con k = 2^n una fórmula para generar números primos. Pero Euler, casi un siglo después se lo estropeó, cuando probó que para n = 5, el número obtenido, 4.294.967.297, no es primo, sino el producto de 6.700.417 x 641. No obstante, también es generadora de muchos números primos

También Euler descubrió las siguientes fórmulas que en principio parecían generar gran cantidad de números primos "n^2 + n + 41" y "n^2 + n + 17 " pero fallaron para n = 40 y para n = 16, dado que producen números compuestos.

Así que, después de mucho tiempo de investigación aún no se ha descubierto una fórmula que permita dar todos los números primos que existen, estos se distribuyen al parecer de forma aleatoria y sin ningún patrón. No obstante, y como hemos visto, si se han ido encontrando algoritmos y/o fórmulas para encontrar una gran cantidad de números primos, y son muchas de ellas junto con la ayuda de los ordenadores las que se usan para descubrir números primos grandes.

El primo más grande que tengo constancia tiene 9.808.358 dígitos de largo, y fue descubierto el 4 de septiembre de 2006. Es un primo de Mersenne, de hecho el número 44. El número en cuestión es "2^32582657 - 1 = 12457502601536945540…11752880154053967871" dónde los puntos suspensivos indican millones de dígitos intermedios.
La Electronic Frontier Foundation ha ofrecido un premio de 100.000 dólares a la primera persona en descubrir un número primo de 10 millones de dígitos o más. ¡Es su oportunidad de hacerse rico y hacerse famoso!

Descárgate un generador de números primos para Windows

No hay comentarios: