¿Qué mecanismo se sigue al encontrar el número primo más grande y cuál es la importancia de encontrar dichos números?

Tales números primos grandes solo tienen valor de curiosidad al menos hoy. Para aplicaciones como el algoritmo RSA donde se usan primos grandes, generalmente solo necesitamos primos de aproximadamente 4096 bits de longitud. Pero el número primo más grande conocido es 57.885.161 bits de longitud, demasiado largo para ser utilizado para cualquier propósito práctico.

Verificar si los números grandes son primos es una tarea computacionalmente intensiva. Fue solo recientemente que se desarrolló un algoritmo de tiempo polinómico determinista (prueba de primalidad AKS) que puede verificar si algún número es primo. Incluso ese algoritmo tiene una complejidad enormemente alta para ser usado prácticamente para verificar la primalidad de números tan grandes.

Lo que nos ayuda es la prueba de primalidad de Lucas-Lehmer. Este es un algoritmo de prueba de primalidad determinista mucho más rápido, pero funciona solo para un tipo especial de números llamados números de Mersenne: estos son números de la forma [math] 2 ^ n-1 [/ math]. ¿Asi que que hacemos? Solo probamos los números grandes de Mersenne para primalidad. Pero incluso esto no es computacionalmente demasiado fácil. Por lo tanto, necesitamos instalaciones informáticas distribuidas para verificar si los números de Mersenne son primos. Esto es lo que hace la Gran Búsqueda de Internet Mersenne Prime (GIMPS): es una instalación de computación distribuida dedicada a probar si los números de Mersenne son primos. Casi todos los números primos más grandes conocidos en los últimos tiempos han sido números de Mersenne encontrados por GIMPS.