thumb|right|Logo de GIMPS
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,Prime95 distribution, undoc.txt 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.TOP500 per November 2012; HP BL460c with 95.1 TFLOP/s (R max). 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 , onde p é um número primo. O menor primo de Mersenne desta tabela é
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º. # Data dedescoberta Primo Mp Quantidadede dígitos Processador Método 35 13 de novembro de 1996 M1 398 269 420.921 Pentium (90 MHz) Prime95 LL 36 24 de agosto de 1997 M2 976 221 895.932 Pentium (100 MHz) 37 27 de janeiro de 1998 M3 021 377 909.526 Pentium (200 MHz) 38 1 de junho de 1999 M6 972 593 2.098.960 Pentium (350 MHz) 39 14 de novembro de 2001 M13 466 917 4.053.946 AMD Athlon T-Bird (800 MHz) 40 17 de novembro de 2003 M20 996 011 6.320.430 Pentium (2 GHz) 41 15 de maio de 2004 M24 036 583 7.235.733 Pentium 4 (2.4 GHz) 42 18 de fevereiro de 2005 M25 964 951 7.816.230 Pentium 4 (2.4 GHz) 43 15 de dezembro de 2005 M30 402 457 9.152.052 Pentium 4 (2 GHz com overclock para 3 GHz) 44 4 de setembro de 2006 M32 582 657 9.808.358 Pentium 4 (3 GHz) 45 6 de setembro de 2008 M37 156 667 11.185.272 Intel Core 2 Duo (2.83 GHz) 46 4 de junho de 2009 M42 643 801 12.837.064 Intel Core 2 Duo (3 GHz) 47 23 de agosto de 2008 M43 112 609 12.978.189 CPU Intel Core 2 Duo E6600 (2.4 GHz) 48 25 de janeiro de 2013 M57 885 161 17.425.170 Intel Core 2 Duo E8400 @ 3.00 GHz 49 7 de janeiro de 2016 M74 207 281 22.338.618 Intel Core i7-4790 50 26 de dezembro de 2017 M77 232 917 23.249.425 Intel Core i5-6600 51 7 de dezembro de 2018 M82 589 933 24.862.048 Intel Core i5-4590T 52 21 de outubro de 2024 M136 279 841 41.024.320 Nvidia A100 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.