Cómo encontrar grandes números primos

La mejor manera de encontrar números primos grandes es usar una cosa llamada «aritmética modular» y otra cosa llamada «teorema de Fermat», no el famoso «último teorema de Fermat». El teorema de Fermat es mucho menos famoso y mucho más útil que el último teorema de Fermat. .

La aritmética modular es cuando hacemos suma, resta y multiplicación con el resto de los números en lugar del número mismo. Entonces, si elegimos una ‘base’ de 10, diríamos que 3 por 4 es 2. Eso es porque si eliges cualquier número que termine en 3 y 4 (es decir, sus restos son 3 y 4 cuando los divides por 10), y multiplíquelos, obtendrá un número cuyo último dígito es 2.

Pruébelo: ¿cuál es el último dígito de 33 x 184? de 103 x 1294? De 239830903 x 29083498954? Siempre es 2.

Si usamos una base de 7 en su lugar, diríamos que 3 x 4 es 5. Si multiplico dos números que dan restos de 3 y 4 cuando los divido por 7, el resultado dará un resto de 5 cuando lo divido por 7.

Eso es aritmética modular. El teorema de Fermat dice que si su base es primo, diga P, y siempre que si elevo A a la potencia de P, obtengo A.

Ejemplos:

si P es 3,

• 1 x 1 x 1 es 1,
• 2 x 2 x 2 es 8, que tiene un resto de 2.

si P es 7,

• 1 ^ 7 es 1,
• 2 ^ 7 es 128, que tiene un resto de 2 cuando divido por 7,
• 3 ^ 7 es 2187, que tiene un resto de 3 cuando divido por 7,
• 4 ^ 7 es 16384, que tiene un resto de 4 cuando divido por 7,
• 5 ^ 7 es 78125, que tiene un resto de 5 cuando divido por 7,
• 6 ^ 7 es 279936, que tiene un resto de 6 cuando divido por 7.

Por otro lado, si P es 10,

• Aunque 1 ^ 10 es 1, por otro lado
• 2 ^ 10 es 1024, que tiene un resto de 4, no 2, cuando divido por 10.

Entonces, si tiene un número N grande y desea verificar si es primo, puede hacer esto:

• asegúrese de que N no tenga factores pequeños; si lo tiene, ¡obviamente no es primo!
• elige tu número favorito A
• calcule A ^ N módulo N (es decir, el resto cuando divide A ^ N por N, hay formas rápidas de hacerlo)
• si no obtienes A, entonces N no es primo.
• si obtiene A, elija una A diferente e intente nuevamente, a menos que ya sepa por teoría que ha verificado suficientes A diferentes para su N. particular

Todos los números primos grandes ahora se basan en trucos como este: el teorema de Fermat o la prueba similar de Lucas-Lehmer.

Si desea encontrar un número primo récord, puede llevar meses de tiempo de computadora verificar un solo número. Como la mayoría de los números no son primos, un cazador en solitario necesitará pasar siglos cazando. Los titulares de los registros hacen el trabajo al reclutar a miles de voluntarios para donar tiempo de computadora no utilizado, de modo que los números primos que rompen récords se descubran de manera brusca una vez cada año o dos. Busque el proyecto GIMPS, por ejemplo, ¡son dueños de los diez de los diez números primos más grandes conocidos!