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.