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.
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 é 2136.279.841−1 (ou M136.279.841, de forma abreviada) e foi descoberto em 12 de outubro de 2024, por Luke Durant. 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.
Algoritmo
Desde a sua concepção até 2018, o projeto dependeu principalmente do teste de primalidade de Lucas–Lehmer (LL), 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 2P−1.
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, 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%.
Em 2018, o GIMPS adotou um teste de primalidade de Fermat com base a=3 como uma opção alternativa para o teste de primalidade, 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. 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. Como resultado, mesmo que o teste LL seja determinístico e o teste de Fermat apenas probabilístico, 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).
Em setembro de 2020, o GIMPS passou a suportar provas de primalidade baseadas em funções de atraso verificáveis (verifiable delay functions) fornecidas por Krzysztof Pietrzak. 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). 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. O PRP e o LL têm tempos de execução semelhantes; a preferência decorre da maior confiança nos resultados do PRP.
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.
História
O projeto começou em janeiro de 1996 com um programa que rodava em computadores i386. O nome do projeto foi cunhado por Luke Welsh, um de seus primeiros pesquisadores e codescobridor do 29º primo de Mersenne. Várias dezenas de pessoas ingressaram em poucos meses e mais de 1.000 ao final do primeiro ano. Joel Armengaud, um participante, descobriu a primalidade do M1.398.269 em 13 de novembro de 1996. 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). Em novembro de 2012, o GIMPS mantinha 95 TFLOPS, garantindo teoricamente ao computador virtual do GIMPS a 330ª posição entre os sistemas de computador mais poderosos do mundo na lista do TOP500. A posição anterior era então ocupada por um 'HP Cluster Platform 3000 BL460c G7' da Hewlett-Packard. 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
Prime95
O software principal usado pelo GIMPS é o Prime95, que implementa todos os algoritmos para uma CPU x86 ou x86-64: fatoração por tentativa (trial factoring, geralmente deixada para as GPUs), PRP, P-1, P+1, ECM e certificação PRP. Embora o código-fonte do software Prime95 esteja publicamente disponível, tecnicamente ele não é um software livre, pois exige que os usuários sigam os termos de distribuição do projeto. Especificamente, se o software for usado para descobrir um número primo com pelo menos 100.000.000 de dígitos decimais, o usuário ganhará apenas US$ 50.000 do prêmio de US$ 150.000 oferecido pela Electronic Frontier Foundation. Por outro lado, o usuário ganhará US$ 3.000 ao descobrir um primo menor que não se qualifique para o prêmio principal.
O GIMPS também "reserva-se o direito de alterar esta EULA (Contrato de Licença de Usuário Final) sem aviso prévio e com efeito retroativo razoável."
Softwares de terceiros
Softwares de terceiros não compartilham das mesmas restrições do Prime95. Eles podem ser usados para aderir ao GIMPS utilizando um programa chamado AutoPrimeNet, que busca as tarefas no GIMPS e devolve os resultados. O software disponível inclui:
Mlucas, que implementa LL, Fermat PRP e o teste de Pépin. Acompanha o MFactor para a fatoração por tentativas. Capaz de rodar em arquiteturas x86, x86-64, ARM e na maioria das outras arquiteturas de CPU. Utiliza IBDWT de precisão dupla.
Glucas, implementação desatualizada de LL para CPUs x86 e não-x86. Utiliza IBDWT de precisão dupla.
GPUowl e PRPLL, programas OpenCL para execução de PRP e LL destinados a GPUs. Utilizam IBDWT de precisão dupla. George Woltman mantém um fork que usa IBDWT em precisão dupla, precisão simples, NTT sobre GF((231−1)2), NTT sobre GF((261−1)2), ou uma combinação desses métodos.
mfaktc (CUDA) / mfakto (OpenCL), programas para fatoração por tentativa em GPU utilizando aritmética de inteiros de 32 bits.
CUDALucas, implementação desatualizada de LL para CUDA. Utiliza IBDWT de precisão dupla.
PrMers/Marin, implementa LL e PRP. Utiliza IBDWT com transformada teórica dos números (NTT) sobre Z/(264−232+1)Z utilizando aritmética de inteiros de 64 bits.
Além disso, o PrimeNet aceita outras formas de contribuição de dados vindas de projetos como o TJOAI (o software personalizado de Tadashi Taura para tentar fatorar simultaneamente muitos números de Mersenne).
Primos encontrados
Todos os primos de Mersenne têm a forma Mp = 2p − 1, onde p é um número primo. O menor primo de Mersenne desta tabela é 21.398.269 − 1.
A primeira coluna é a classificação do primo de Mersenne na sequência (ordenada) de todos os primos de Mersenne; O GIMPS encontrou todos os primos de Mersenne conhecidos começando a partir do 35º.
Gpuowl PRP (verificado usando LL no Prime95, PRPLL, CUDALucas, etc.)
^ † 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º (M77232917) e o 52º (M136279841) 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.
^ ‡ O número M136279841 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.
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 M74207281 foi relatado ao servidor em 17 de setembro de 2015, mas o relatório passou despercebido até 7 de janeiro de 2016.
Notas
↑a=2 não funcionaria, pois todos os números de Mersenne são 2-pseudoprimos.
↑Não está provado nem refutado que pseudoprimos de Mersenne na base 3 existam.
↑Para entender a justificativa por trás dessa busca, consulte o projeto relacionado Projeto Cunningham.
↑Woltman, George. «mersenneforum.org - Drought ends! (M52 Found)». Consultado em 6 de novembro de 2025. Cópia arquivada em 25 de maio de 2025. Prime95: Hoje, um novo primo provável de Mersenne foi relatado ao servidor! A prova de PRP foi rapidamente certificada, provando que não houve erros durante os cálculos. Testes de LL usando o prime95 e o prpll estão em andamento. Talvez um teste LL Mlucas também devesse ser executado. A verificação provavelmente levará alguns dias. Redigir um comunicado de imprensa e encontrar um meio de comunicação interessado também levará algum tempo. Até lá, o expoente não será anunciado. [...] (as respostas incluem várias execuções independentes do LL)
