Verificador de Mersenne

Quando o próprio Mp é primo, chama-se primo de Mersenne — números que impulsionaram buscas de recorde por séculos, desde as primeiras listas de Marin Mersenne até os projetos distribuídos modernos. Nem todo expoente produz um primo: se p é composto então Mp é composto, e mesmo para muitos expoentes primos o número de Mersenne se fatore (por exemplo 2^11 − 1 = 2047 = 23 × 89). Esta ferramenta recebe um expoente inteiro p pelo menos dois, retorna o valor decimal completo de 2^p − 1 como string e decide se esse valor é primo com o teste determinístico de Lucas-Lehmer quando p é um primo ímpar.

O que são números de Mersenne e como Lucas-Lehmer decide

Um número de Mersenne é definido por um único expoente: Mp é dois elevado à potência p, menos um. Os primeiros valores são constantes familiares de sala — M2 vale três, M3 sete, M5 trinta e um, M7 cento e vinte e sete — enquanto expoentes maiores produzem inteiros com milhares de dígitos decimais. Um primo de Mersenne é simplesmente um número de Mersenne que é primo.

Uma condição necessária clássica é que o próprio expoente p seja primo: se p se fatore como ab com a e b maiores que um, então 2^a − 1 divide 2^{ab} − 1, de modo que Mp não pode ser primo. Essa condição necessária não é suficiente. Para p igual a onze, que é primo, M11 vale dois mil e quarenta e sete e se fatore como vinte e três vezes oitenta e nove.

O teste de Lucas-Lehmer resolve a questão completamente para expoentes primos ímpares. Comece com s zero igual a quatro; em cada um dos próximos p menos dois passos substitua s por s ao quadrado menos dois, reduzido módulo Mp. O número de Mersenne é primo se e somente se o resíduo final for zero.

Para o caso especial p igual a dois o número três é primo por inspeção e não precisa da sequência iterativa. Esta capacidade implementa esse pipeline exato com aritmética BigInt: nunca aproxima, nunca chama um serviço de primalidade e nunca depende do relógio de parede ou de bits aleatórios. Você sempre obtém o mesmo booleano para o mesmo p.

Onde checagens de Mersenne aparecem no trabalho real

Programadores de competição e treinadores de olimpíada usam pequenas checagens de Mersenne como aquecimento antes de problemas mais duros de aritmética modular, e precisam de um oráculo determinístico do qual os alunos não possam divergir acidentalmente de uma fórmula de planilha. Engenheiros de criptografia e sistemas às vezes validam demos didáticas ou tabelas históricas de primos de Mersenne conhecidos sem reivindicar força criptográfica a partir de uma única sequência modular.

Se mais tarde precisar de pares gêmeos, π(n) ou fatoração de um composto geral, trate-os como intenções de busca separadas em vez de sobrecarregar esta página focada em Mersenne. Números de Mersenne continuam sendo a página certa quando a pergunta é quanto vale 2^p − 1 e se Lucas-Lehmer (ou a regra do expoente composto) o certifica como primo de Mersenne.