Premessa

I numeri primi sono una parte importante della matematica e sono stati studiati per millenni. Un numero primo è un numero naturale, strettamente maggiore di 1, che è divisibile solo per 1 e per se stesso. Essi sono elementi di base nella teoria dei numeri e sono usati in molte applicazioni pratiche, come la crittografia e la generazione di numeri casuali. La ricerca dei numeri primi ha una storia lunga e una profonda influenza sulla matematica moderna. 

Ciò nonostante, oggi esistono ancora numerose proprietà riguardanti i numeri primi, ancora da provare, dimostrare o eventualmente smentire.

Definizione

Iniziamo con una definizione formale: un numero primo è un numero intero positivo diverso da 1 che non è divisibile per alcun altro numero intero positivo diverso da 1 e da se stesso. Ad esempio, i numeri 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 sono tutti primi. Un modo semplice per determinare se un numero è primo è quello di verificare tutti i numeri interi inferiori a quello dato per vedere se sono divisori, e se non lo sono allora è primo. 

Algoritmi e test di primalità

Il crivello di Eratostene è un algoritmo di ricerca usato per trovare tutti i numeri primi fino a un certo valore. Si basa sull'idea che tutti i numeri non primi sono divisibili per qualche numero primo più piccolo. Pertanto, l'algoritmo divide un insieme di numeri in due parti: quelli primi e quelli non primi. Inizia eliminando tutti i multipli del più piccolo numero primo (2). Quindi, rimuove tutti i multipli del successivo numero primo (3), e così via. Alla fine, tutti i numeri rimasti saranno primi.

Un'altra importante tecnica è la ricerca di numeri primi più grandi, nota come ricerca di numeri primi di Wilson. Questa tecnica è stata utilizzata per scoprire il più grande numero primo scoperto finora, che contiene 23.249.425 cifre. 

A cosa serve studiare i numeri primi

I numeri primi sono molto interessanti: sono i mattoni fondamentali della matematica e sono usati in tutti i tipi di applicazioni.
Oltre ad essere utili nella teoria dei numeri, hanno una profonda influenza sulla crittografia. La sicurezza della maggior parte dei sistemi di criptazione si basa sull'assunzione che sia difficile trovare i numeri primi di cui sono composti. Per questo motivo, l'utilizzo di numeri primi è fondamentale per la sicurezza di tutti i tipi di informazioni digitali. 

L'ordine dei numeri primi

La maggior parte dei matematici credono che i numeri primi siano distribuiti in modo casuale, senza un ordine o un disordine percepibili. Pensano che non c'è un modello o una regola che governa la sequenza di questi numeri.

Personalmente, io mi associo ai pochi matematici che credono in un ordine nella distribuzione dei numeri primi e che questi numeri possano essere predetti con gli giusti strumenti matematici.
In una famosa citazione, Galileo recita: “La matematica è l'alfabeto nel quale Dio ha scritto l'universo”.
Cerco di spiegare di seguito il mio punto di vista riguardo ai numeri primi e al loro ordine.

Il mio approccio

Abbiamo 10 dita: questa è una caratteristica fisica cha ha condizionato e continua a condizionare qualsiasi studio facciamo. Ogni cosa la riportiamo al sistema decimale perché ci è comodo da utilizzare.
Sicuramente questo approccio ci ha aiutato in numerosissime occasioni, ma bisogna riconoscere che in alcune situazioni, di natura completamente diversa, riportare tutto allo studio regolamentato da questo sistema, ci potrebbe far sfuggire dettagli importanti per la comprensione del fenomeno.
Inizio quindi subito affermando che il sistema migliore per comprendere i numeri primi è quello di costruire un sistema numerico che segua la naturale evoluzione di questi numeri.

Ragioniamo per step:
I primi 2 numeri primi sono 2 e 3. Per questo motivo consiglio di iniziare a ragionare su un sistema numerico a base 6.

I primi 6 numeri sono:

01, 02, 03, 04, 05, 10.

Si noti che 10 in base sei è sei, non dieci.

02 è primo, 03 e primo, mentre 04 e 10 (sei in base sei) sono le combinazioni lineari di 02 e 03 all'interno di questo periodo.

Il primo vantaggio che si evidenzia da un sistema numerico di questo tipo è che qualsiasi numero rappresentato in base 6 che finisce in 2, 3, 4 o 0, non è primo perchè scomponibile con i fattori primi 2 e/o 3. Vi spiego come si verifica questa situazione.
Il fatto che questo sistema numerico ha un ciclo esattamente uguale al prodotto dei 2 numeri primi, fa si che anche nei cicli successivi, nelle stesse posizioni in cui capitano questi 2 numeri e nelle posizioni in cui capitano le combinazioni lineari del primo ciclo, ci saranno sempre numeri multipli di 2 o di 3.

I numeri primi, quindi, avranno necessariamente sempre come ultima cifra in base sei, o 1 o 5. Attenzione: non tutti i numeri che finiscono con 1 o 5 sono primi: si tratta di una condizione necessaria, ma non sufficiente!

Riguardo a questo aspetto, Gauss ha dimostrato che tutti i numeri primi si possono scrivere sotto le forme 6n + 1 o 6n - 1.

Quanto enunciato si dimostra facilmente: partiamo dal presupposto che tutti i numeri si possano scrivere come 6n + a, con a = 0, ±1, ±2, ±3, ±4 e ±5.

Se a = 0, allora 6n + 0 = 6n, il che significa che 6n è divisibile per 6, e quindi non è un numero primo.

Se a = ±1, allora 6n + 1 o 6n - 1, che sono entrambi numeri potenzialmente primi. In particolare di questi numeri sappiamo che non sono divisibili ne per 2, ne per 3.

Se a = ±2, allora 6n + 2 o 6n - 2. 6n + 2 è sempre divisibile per 2 ed il risultato della divisione è 3n+1.
Trattandosi di un sistema ciclico, 6n - 2 equivale a 6(n-1) + 4 che diviso 2 da come risultato 3(n-1) + 2.

Se a = ±3, allora 6n + 3 o 6n - 3, seguendo la stessa logica esposta prima, sono divisibili sempre per 5, quindi non sono mai numeri primi. 

Se a = ±4, allora 6n + 4 o 6n - 4, sono divisibili per 2 e quindi non sono numeri primi. 

Se a = ±5, allora 6n + 5 o 6n - 5, corrispondono a 6(n+1) - 1 e 6(n-1) +1, e quindi possono essere primi.

Abbiamo quindi una sorta di "matrice" che, ripetuta, crea una sorta di crivello che evidenzia i numeri scomponibili per i fattori primi 2 e 3.
Per semplicità, chiamerò questa "matrice" di 6 elementi "matrice generatrice" di ordine 6 (2x3).

La matrice generatrice crescente

Dal paragrafo precedente abbiamo estratto una matrice fatta di 6 elementi (6x1), con numeri da 1 a 6 che, se ripetuta, ci permette di individuare i numeri divisibili per 2 e 3, quindi scomponibile con i fattori primi 2 e 3. Riportiamo in arancione le posizioni nelle quali rientrano i numeri sicuramente non primi:

| 1 | 2 | 3 | 4 | 5 | 6 | 

Escludendo il valore 1, il primo numero successivo all'ultimo numero primo individuato (il 3), potenzialmente primo (il 5) sarà sicuramente primo in quanto non è divisibile per 2 e/o per 3, e non esiste nessun altro numero primo dopo 2 e 3 per cui 5 è divisibile.

Avendo un nuovo numero sicuramente primo, potremmo creare una nuova matrice generatrice di ordine (2x3)x5 = 30, in questo modo:

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|

a questo punto elimino dalla matrice le combinazioni lineari del nuovo primo individuato, che rientrano nel periodo di 30 elementi. Per iniziare rendo arancione il 5 stesso. Come vediamo, le combinazioni lineari tra 5 e i numeri primi che lo precedono (2 e 3) sono già arancioni in quanto multipli degli stessi primi che lo anticipo. Di conseguenza dopo aver colorato in arancione il numero 5, il primo successico è sempre e sicuramente il suo quadrato: 5x5=25. Quello ancora successivo sarebbe 5*7 (5 per il primo successivo) che però, uscendo dal periodo non va considerato. A questo punto abbiamo concluso la trasformazione della matrice di ordine 30 per la replica.
Faccio notare che 5x7=(5x6)+(5x1) dove 5x6 è la lunghezza del periodo e la posizione 5 della ripetizione successiva della matrice è già arancione. Stessa cosa per le combinazioni successive, infatti 5x11=(5x6)+(5x5)= periodo + 25. Questo, in sintesi, significa che nelle ripetizioni della matrice generatrice di ordine 30, il lavoro di coprire i multipli di 5 è "gratuito" in quanto già fatto alla fonte.
Si noti come si evitano elegantemente operazioni inutili: tutte le combinazioni lineari che individuiamo non sono mai nàmeri gia resi arancioni.

Ecco il periodo dopo aver applicato le azioni del numero primo 5:

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|

questa nuova matrice, di ordine 30, ripetuta all'infinito, individua tutti i numeri scomponibili in fattori primi con i fattori 2, 3 e 5.

Un'altro aspetto interessante è che tutti i numeri in nero <25 sono sicuramente primi in quanto non esiste nessun numero che abbia fattori primi >5 che sia minore di 25. 

È possibile reiterare questo procedimento facendo crescere progressivamente la matrice che diventerà nello step successivo 30 x 7 = 210, ed in quella dopo 210 x 11 = 2310, e così via.

Riassumendo

Siamo partiti dai primi 2 numeri primi: 2 e 3; e dalla prima matrice lunga quanto la loro combinazione 2x3=6.

Il primo numero primo successivo individuato (prima casella nera dopo il 3) è 5. Ora i numeri primi sono 2,3 e 5.

Si elimina dalla nuova matrice generatrice tutti i numeri che nascono dalla combinazione lineare di 5 ed i primi >=5. 

Il procedimento si reitera.

La prima operazione che facciamo in ogni step è quella di "copiare" il periodo un numero di volte uguale al numero primo successivo a quello individuato. Questa operazione impiega N passaggi.

Poi vengono esaminati tutti i numeri > del nuovo numero primo (operazione di un numero di passaggi maggiorata da N), e si eliminano tutte le combinazioni lineari tra il nuovo primo e i successivi "numeri neri" che lo seguono, finchè i risultati di tali prodotti siano inferiori alla lunghezza del periodo. Anche questa operazione ha un numero di passaggi elementari maggiorati da N.

Il numero di operazioni totali dell'algoritmo è maggiorata da 3N quindi la complessità è N.

Questo metodo ricorda il famoso crivello di Eratostene, ma si noti che ogni operazione, elimina dal periodo esattamente un numero dalla matrice; in altre parole non esistono operazioni "inutili" che fanno crescere il numero di operazioni e quindi la complessità.

Proviamo in pratica

Se ad esempio volessimo trovare tutti i numeri primi <100 operiamo come segue.

Il primo periodo è rappresentato dalla matrice di ordine 6:

 1 | 2 | 3 | 4 | 5 | 6 | 

ed i numeri primi noti sono 2 e 3.

Partendo da 3 scorriamo in avanti fino a trovare il primo numero nero. Il numero è 5 ed abbiamo impiegato 2 passaggi.

Accodiamo ora altre 4 volte (5 in tutto) la matrice di seguito per ottenere la nuova:

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|

Costo dell'operazione: 24 passaggi elementari; totale 26 (2+24).

Facciamo diventare il 5 arancione ed anche il 5x5. 5x7 è>30 per cui lo scartiamo e ci fermiamo. Abbiamo fatto altri 3 passaggi per arrivare a 29, ottenendo la seguente matrice:

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|

Partendo da 5  cerchiamo il numero primo successivo (7) che viene aggiunto alla lista dei primi trovati (2, 3, 5, 7). 2 passaggi per un totale di 31.

dovremmo ripetere il periodo fino a 210, ma siccome il nostro scopo è trovare i primi <100, ci fermiamo a 100. 70 passaggi + 31, e siamo a 101. Ora abbiamo una matrice così:

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41|42|43|44|45|46|47|48|49|50|51|52|53|54|55|56|57|58|59|60|61|62|63|64|65|66|67|68|69|70|71|72|73|74|75|76|77|78|79|80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|96|97|98|99|100|

Si eliminano le combinazioni lineari tra i primi a partire da 7: 7, 7x7=49, 7x11=77, 7*13=91, infine 7x17 fa 119 che supera N, per cui ci fermiamo. Con le nuove 10 operazioni la complessità è arrivata a 111.

Ecco la matrice dopo l'applicazione del 7:

|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20|21|22|23|24|25|26|27|28|29|30|31|32|33|34|35|36|37|38|39|40|41|42|43|44|45|46|47|48|49|50|51|52|53|54|55|56|57|58|59|60|61|62|63|64|65|66|67|68|69|70|71|72|73|74|75|76|77|78|79|80|81|82|83|84|85|86|87|88|89|90|91|92|93|94|95|96|97|98|99|100|

Siccome le combinazioni lineari del primo successivo sono > N (11x11=121 e le successive sono anche maggiori), tutti i numeri rimasti in nero sono primi per cui aggiungiamo alla nostra lista 2, 3, 5, e 7, i numeri:

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 e 97

con un dispendio di ulteriori 89 passaggi per un totale di esattamente 200: solo 200 passaggi per trovare tutti i numeri primi <=100.

Conclusione

Senza smorzare l'entusiasmo, desidererei circoscrivere il campo di applicabilità di questa metodologia di ricerca dei numeri primi; efficiente ma utilizzabile solo in specifici contesti.

Inizio affermando che non si tratta di un test di primalità: il limite di questa metodologia è rappresentato prevalentemente dalla necessità di mantenere memorizzata tutta la matrice di ordine N (che cresce esponenzialmente).
In altre parole, con questo algoritmo, senza prima aver percorso tutto il processo per avere i numeri primi <N, non è possibile sapere se N è primo o meno. 

Se invece desideriamo individuare i primi N numeri primi, alle mie risultanze, è il miglior algoritmo a disposizione.

Detto ciò, desidero aggiungere che la ricerca dei primi numeri primi non è lo scopo principale per cui ho costruito questo algoritmo. Questo strumento è stato pensato per permettere una migliore comprensione di come si "costruiscono" i numeri primi. Si mette a disposizione di ulteriori studi, sempre riguardanti in numeri primi, ma con altre finalità.
Vedremo, in articoli che seguiranno, che aver compreso con questi concetti base ci permetterà di dimostrare numerose caratteristiche dei numeri primi.

Chiudo ribadendo che i numeri primi hanno una loro armonia, complessa da individuare, ma precisa e ordinata, e che, per essere compresa, richiede il giusto punto di vista ed il giusto mindset.