I primi di Mersenne e il test di Lucas-Lehmer

Negli ultimi anni i primi di Mersenne sono saliti alla ribalta delle cronache in più di un'occasione, in concomitanza della scoperta di nuovi elementi per via delle loro dimensioni da record che superano di molti ordini di grandezza i primi non appartenenti a questa classe. Questo lavoro vuole affrontare l'argomento dei primi di Mersenne e del test ideato da Édouard Lucas e migliorato da Derrick Lehmer da un punto di vista che concili il rigore delle dimostrazioni con le sfaccettature delle applicazioni che ne sono conseguite. Nel primo capitolo viene affrontato l'argomento dei numeri di Mersenne e delle loro proprietà, ponendo l'attenzione anche sull'evoluzione storica delle conoscenze che hanno permesso lo sviluppo della matematica moderna. Il secondo capitolo si concentra sul test di Lucas-Lehmer che, grazie all'avvento dei calcolatori elettronici, ha allargato gli orizzonti della ricerca dei numeri primi oltre i limiti dei test di primalità generali. Oltre all'analisi del teorema, viene anche considerato il problema dell'implementazione computazionale dell'algoritmo, con particolare attenzione alle possibilità di ridurre il costo della verifica, sia in termini di tempo che di operazioni e di spazio occupato. Vengono infine riportate alcune proprietà algebriche necessarie alla trattazione, seguite da una panoramica dell'implementazione del test da parte del progetto di calcolo distribuito GIMPS. In seguito si trova una discussione parallela al primo capitolo sui numeri di Fermat, strettamente imparentati con i numeri di Mersenne.