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.
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.
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.
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.
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 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.