Verificatore di Mersenne

Quando lo stesso Mp è primo si chiama primo di Mersenne — numeri che hanno guidato ricerche di record per secoli, dalle prime liste di Marin Mersenne ai moderni progetti distribuiti. Non ogni esponente produce un primo: se p è composto allora Mp è composto, e anche per molti esponenti primi il numero di Mersenne si fattorizza (ad esempio 2^11 − 1 = 2047 = 23 × 89). Questo strumento prende un esponente intero p almeno due, restituisce il valore decimale completo di 2^p − 1 come stringa e decide se quel valore è primo con il test deterministico di Lucas-Lehmer quando p è un primo dispari.

Cosa sono i numeri di Mersenne e come decide Lucas-Lehmer

Un numero di Mersenne è definito da un solo esponente: Mp è due elevato alla potenza p, meno uno. I primi valori sono costanti familiari in aula — M2 vale tre, M3 sette, M5 trentuno, M7 centoventisette — mentre esponenti maggiori producono interi con migliaia di cifre decimali. Un primo di Mersenne è semplicemente un numero di Mersenne che è primo.

Una condizione necessaria classica è che l’esponente p stesso sia primo: se p si fattorizza come ab con a e b maggiori di uno, allora 2^a − 1 divide 2^{ab} − 1, quindi Mp non può essere primo. Quella condizione necessaria non è sufficiente. Per p uguale a undici, che è primo, M11 vale duemilaquarantasette e si fattorizza come ventitré per ottantanove.

Il test di Lucas-Lehmer risolve completamente la questione per esponenti primi dispari. Parta da s zero uguale a quattro; per ciascuno dei successivi p meno due passi sostituisca s con s al quadrato meno due, ridotto modulo Mp. Il numero di Mersenne è primo se e solo se il residuo finale è zero.

Per il caso speciale p uguale a due il numero tre è primo per ispezione e non richiede la sequenza iterativa. Questa capacità implementa quel pipeline esatto con aritmetica BigInt: non approssima mai, non chiama mai un servizio di primalità e non dipende mai dall’orologio di parete o da bit casuali. Ottiene sempre lo stesso booleano per lo stesso p.

Dove compaiono i controlli di Mersenne nel lavoro reale

Programmatori di gara e coach di olimpiadi usano piccoli controlli di Mersenne come riscaldamento prima di problemi più duri di aritmetica modulare, e hanno bisogno di un oracolo deterministico da cui gli studenti non possano divergere accidentalmente da una formula di foglio di calcolo. Ingegneri di crittografia e sistemi a volte validano demo didattiche o tabelle storiche di primi di Mersenne noti senza rivendicare forza crittografica da una sola sequenza modulare.

Se più avanti Le servono coppie gemelle, π(n) o fattorizzazione di un composto generale, li tratti come intenzioni di ricerca separate invece di sovraccaricare questa pagina incentrata su Mersenne. I numeri di Mersenne restano la pagina giusta quando la domanda è quanto vale 2^p − 1 e se Lucas-Lehmer (o la regola dell’esponente composto) lo certifica come primo di Mersenne.