Nota: Não confundir com GIMP.

A Great Internet Mersenne Prime Search (GIMPS) é um projeto colaborativo de voluntários que usam um software gratuito e amplamente disponível para buscar números primos de Mersenne.

O GIMPS foi fundado em 1996 por George Woltman, que também escreveu o cliente Prime95 e sua versão portada para Linux, o MPrime. Scott Kurowski escreveu o servidor back-end PrimeNet para demonstrar o software de computação voluntária da Entropia, uma empresa que ele fundou em 1997. O GIMPS é registrado como Mersenne Research, Inc., tendo Kurowski como Vice-Presidente Executivo e membro do conselho de diretores. Diz-se que o GIMPS é um dos primeiros projetos de computação voluntária em larga escala através da Internet para fins de pesquisa.^[1]

Até outubro de 2024, o projeto já havia encontrado 18 primos de Mersenne, 16 dos quais eram o maior número primo conhecido na época em que foram descobertos. O maior número primo conhecido é 2^136.279.841 − 1 (ou M_136.279.841, de forma abreviada) e foi descoberto em 12 de outubro de 2024, por Luke Durant.^[2][3] Em 18 de junho de 2025, o projeto ultrapassou um marco importante após todos os expoentes abaixo de 136.279.841 terem sido verificados pelo menos uma vez.^[4]

Algoritmo

Desde a sua concepção até 2018, o projeto dependeu principalmente do teste de primalidade de Lucas–Lehmer (LL),^[5] um algoritmo que é tanto especializado para testar primos de Mersenne quanto particularmente eficiente em arquiteturas de computador com sistema binário. Antes de aplicá-lo a um dado número de Mersenne, havia uma fase de divisão por tentativa, usada para eliminar rapidamente muitos números de Mersenne com fatores pequenos. O algoritmo p − 1 de Pollard também é usado para buscar fatores suaves. A variante de LL usada na implementação principal (Prime95) baseia-se especificamente na transformada discreta ponderada de base irracional com números de ponto flutuante de precisão dupla, que fornece uma maneira eficiente de elevar ao quadrado um número grande em módulo 2^P − 1.^[6]

Um cuidado especial é tomado para garantir que o uso de números de ponto flutuante não introduza erros no cálculo de LL. O programa verifica se o erro de arredondamento não é superior a 0,4 a cada 128 iterações, ou se o expoente sendo testado está dentro de 0,5% do tamanho máximo de expoente que pode ser processado pelo tamanho da FFT em uso (ou caso seja solicitado usando uma opção especial), a cada única iteração. A cada 12 horas, o programa executa uma verificação de erro adicional baseada no símbolo de Jacobi,^[7] com uma chance de 50% de detectar um erro. Além disso, cada cálculo LL concluído é repetido por um hardware diferente para "verificação dupla" (double-checking). Com base no histórico de dados de verificação dupla, cada cálculo LL sem qualquer erro grave relatado teve uma taxa de erro de 1,5%; aqueles com pelo menos um erro grave relatado tiveram uma taxa de erro de 50%.^[6]

Em 2018, o GIMPS adotou um teste de primalidade de Fermat com base a = 3^[a] como uma opção alternativa para o teste de primalidade,^[9] ao mesmo tempo em que manteve o teste LL como uma verificação dupla para números de Mersenne detectados como primos prováveis pelo teste de Fermat.^[10] Este novo teste é chamado de PRP (primo provável) na linguagem do GIMPS. Utilizando um método desenvolvido por Robert Gerbicz, o GIMPS pode ter "99,999+%" de certeza de que um resultado PRP é gerado corretamente.^[6] Como resultado, mesmo que o teste LL seja determinístico e o teste de Fermat apenas probabilístico,^[b] a probabilidade de o teste de Fermat encontrar um pseudoprimo de Fermat que não seja primo é muito menor do que a taxa de erro do teste LL devido a erros no hardware do computador (soft errors).^[11]

Em setembro de 2020,^[12][13][14] o GIMPS passou a suportar provas de primalidade baseadas em funções de atraso verificáveis (verifiable delay functions) fornecidas por Krzysztof Pietrzak.^[15] Os arquivos de prova são gerados enquanto o teste de primalidade de Fermat está em andamento. Essas provas, juntamente com o algoritmo de verificação de erros de Gerbicz, fornecem total confiança na exatidão do resultado do teste e eliminam a necessidade de verificações duplas (a verificação da prova poderia ser executada em 1/100 do tempo do cálculo original de Fermat).^[6] Os testes LL de primeira vez foram descontinuados em abril de 2021, deixando o LL para ser usado apenas nos primos prováveis encontrados pelo teste de Fermat.^[16] O PRP e o LL têm tempos de execução semelhantes;^[17] a preferência decorre da maior confiança nos resultados do PRP.^[16]

O GIMPS também tem subprojetos para fatorar números compostos conhecidos de Mersenne e números de Fermat. Estes utilizam a fatoração de curvas elípticas (ECM) e o algoritmo p + 1 de Williams.^[18][c]

História

O projeto começou em janeiro de 1996^[19][20] com um programa que rodava em computadores i386.^[21][22] O nome do projeto foi cunhado por Luke Welsh, um de seus primeiros pesquisadores e codescobridor do 29º primo de Mersenne.^[23] Várias dezenas de pessoas ingressaram em poucos meses e mais de 1.000 ao final do primeiro ano.^[22][24] Joel Armengaud, um participante, descobriu a primalidade do M_1.398.269 em 13 de novembro de 1996.^[25] Desde então, o GIMPS tem descoberto um novo número primo de Mersenne a cada 1 a 2 anos, em média, mas o maior número primo mais recente, encontrado em outubro de 2024, levou quase seis anos para ser encontrado.

Status

Até julho de 2022, o GIMPS registrava uma taxa de transferência (throughput) agregada média sustentada de aproximadamente 4,71 PetaFLOPS (ou PFLOPS).^[26] Em novembro de 2012, o GIMPS mantinha 95 TFLOPS,^[27] garantindo teoricamente ao computador virtual do GIMPS a 330ª posição entre os sistemas de computador mais poderosos do mundo na lista do TOP500.^[28] A posição anterior era então ocupada por um 'HP Cluster Platform 3000 BL460c G7' da Hewlett-Packard.^[29] A partir dos resultados da TOP500 de julho de 2021, os números atuais do GIMPS não fariam mais parte da lista.

Essa capacidade era de cerca de 50 TFLOPS no início de 2010, 30 TFLOPS em meados de 2008, 20 TFLOPS em meados de 2006 e 14 TFLOPS no início de 2004.

Software

Primos encontrados

Todos os primos de Mersenne têm a forma M_p = 2^p − 1, onde p é um número primo. O menor primo de Mersenne desta tabela é 2^1.398.269 − 1.

A primeira coluna é a classificação do primo de Mersenne na sequência (ordenada) de todos os primos de Mersenne;^[35] O GIMPS encontrou todos os primos de Mersenne conhecidos começando a partir do 35º.

^{^ †} A partir de 13 de maio de 2026, 80.504.321 é o maior expoente abaixo do qual todos os outros expoentes primos foram verificados duas vezes, portanto, não se sabe ainda se existem números primos de Mersenne não descobertos entre o 50º (M_77232917) e o 52º (M_136279841) nesta tabela; portanto, a classificação é provisória. Além disso, 140.063.639 é o maior expoente abaixo do qual todos os outros expoentes primos foram testados pelo menos uma vez, portanto, todos os números de Mersenne abaixo do 52º primo de Mersenne foram testados.^[37]

^{^ ‡} O número M_136279841 tem 41.024.320 dígitos decimais. Para ajudar a visualizar o tamanho desse número, se ele fosse salvo no disco rígido, o arquivo de texto resultante teria quase 42 megabytes de tamanho (a maioria dos livros em formato de texto puro tem menos de dois megabytes). O layout padrão de um processador de texto (50 linhas por página, 75 dígitos por linha) exigiria 10.940 páginas para exibi-lo. Se fosse impresso usando papel de impressora padrão, com texto apenas de um lado, seriam necessárias aproximadamente 22 resmas (22 × 500 = 11.000 folhas) de papel.

Como mencionado acima, todo resultado do teste de Lucas-Lehmer passa por uma verificação dupla (double-checking) para evitar falsos positivos e falsos negativos. Resultados positivos recebem maior escrutínio. A importância disso foi ilustrada em 2003, quando um falso positivo foi relatado ao servidor como sendo um primo de Mersenne, mas a verificação posterior falhou.^[38]

A "data de descoberta" oficial de um número primo é a data em que um humano notou pela primeira vez o resultado para o primo, o que pode diferir da data em que o resultado foi inicialmente relatado ao servidor. Por exemplo, o M_74207281 foi relatado ao servidor em 17 de setembro de 2015, mas o relatório passou despercebido até 7 de janeiro de 2016.^[39]

Notas

Referências

Ligações externas

• www.mersenne.org
• primes.utm.edu
• mersennewiki.org
• Mersenne Wiki