Encontre o primeiro megaprimo e ganhe US$ 50k

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxx>]

Oi gente, só queria ter certeza que todos conhecem esta "campanha":
quem encontrar o primeiro primo com >= 1000000 algarismos (na base 10)
ganha US$ 50k da Eletronic Frontier Foundation (espero não ter errado o
nome).

O mais fácil é que para participar não é sequer necessário saber
programar: no endereço www.mersenne.org há programas para vários OS
(entre outros Linux e aquele outro OS com a tela azul)
que procuram primos de Mersenne (primos da forma 2^p - 1)
usando o critério de Lucas-Lehmer.
O critério de Lucas-Lehmer é o seguinte:

Seja p primo, p >= 3 e seja s(0) = 4, s(n+1) = (s(n))^2 - 2,
de tal forma que s(1) = 14, s(2) = 194, ...\dots
Então M_p = 2^p - 1 é primo se e somente se s(p-2) é múltiplo de M_p.

Fica como exercício para vocês provar que 2^p - 1 só pode ser primo
se p é primo. Vocês também podem tentar demonstrar o critério de LL.

Os primos de Mersenne conhecidos são 2^p - 1 para p =
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203,
2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497,
86243, 110503, 132049, 216091, 756839, 859433,
1257787, 1398269, 2976221, 3021377

Os últimos 6 desta lista são também os 6 maiores primos conhecidos.

[]s, N.