Mersenne, successione di
Mersenne, successione di
Mersenne, successione di espressione con cui si indica la successione di numeri naturali Mn = 2n − 1. I numeri che compaiono all’interno della successione di Mersenne sono detti numeri di Mersenne: per esempio M1 = 1, M2 = 3, M3 = 7. Particolare rilievo spetta ai numeri primi che compaiono nella successione di Mersenne: tali primi sono detti primi di Mersenne. Sono per esempio primi di Mersenne M2 = 3, M3 = 7 e M5 = 31, mentre per esempio M4 = 15 non lo è. In generale, se Mn è primo, allora anche n lo è; dunque i primi di Mersenne vanno ricercati considerando solamente gli indici che sono a loro volta numeri primi. Un problema tuttora aperto è se i primi di Mersenne siano o meno in numero finito; la ricerca di nuovi primi di Mersenne è tuttavia un procedimento computazionalmente molto oneroso. La possibilità di disporre di numeri primi molto grandi permette di sviluppare metodi di crittazione dei dati sempre più sicuri; tuttavia la quantità di calcoli richiesta per verificare la primalità di un numero molto grande è proibitiva (→ crittografia). I numeri di Mersenne sono oggetto di studio perché esiste un criterio, detto test di Lucas-Lehmer, dai nomi del matematico francese Édouard Lucas (1842-91), che lo ideò nel 1870, e del matematico statunitense Derrick Norman Lehmer (1867-1938), che lo semplificò nel 1930, che fornisce una condizione necessaria e sufficiente affinché un numero di Mersenne sia primo: Mn è primo se e solo se Mn divide Wn, dove Wn è il termine di indice n della successione così definita per ricorrenza: W2 = 4, Wn+1 = Wn2 − 2 (per n ≥ 3) e i cui primi termini sono perciò 4, 14, 194, ... Sulla base di tale criterio è possibile costruire un algoritmo che permette di verificare la primalità di un numero di Mersenne con una quantità di calcoli che è compatibile con la potenza attuale dei calcolatori; il più grande numero primo conosciuto è proprio un numero di Mersenne.