Ipotesi di non-casualità dei numeri primi

Salve amici, oggi parleremo di numeri primi.
Partiamo dal concetto di numero primo: un intero naturale n si definisce primo se i suoi divisori sono solo 1 e n stesso.
La sequenza iniziale dei numeri primi inizia in questo modo: 2,3,5,7,11,13,17,19,23,.....
Ora, trovare un ordine all'interno di questa sequenza vuol dire trovare una qualche particolare proprietà che può essere ritenuta "interessante" nella sequenza stessa, oltre naturalmente a quella di essere numeri primi.
Bene, la prima proprietà riguarda il fatto di sapere se i numeri primi sono infiniti o meno.
Man mano che i numeri interi aumentano, si trovano meno numeri primi: questo accade perché è più facile trovare un intero molto grande che possa essere diviso da un intero più piccolo, dando resto nullo.
Si potrebbe pensare, dunque, che, da un certo punto in poi, non ci siano più numeri primi e che tutti gli interi siano divisibili per altri più piccoli.
In realtà le cose non stanno in questo modo: si può dimostrare che scegliendo un intero grande a piacere, esiste un numero primo più grande di esso, ossia esistono infiniti numeri primi.
Si tratta di una proprietà molto interessante: significa che esistono interi grandi quanto volete che non possono essere divisi per alcun intero più piccolo.
In modo più "diradato", più "rarefatto", certamente, ma esistono.
Sarebbe, però, anche interessante conoscere come sono distribuiti i numeri primi tra tutti gli interi.
Facciamo un esempio coi numeri pari: 2,4,6,8,10,12,14,....: il terzo numero pari è 6 mentre il settimo numero pari è 14.
E' facilissimo dimostrare che l'n-esimo numero pari è 2*n; ad esempio, il centesimo numero pari è 200.
E' possibile trovare una formula simile anche per i numeri primi ?
Ci provò Eulero intorno al 1751, senza riuscirci. In effetti, se guardiamo le tavole della successione dei numeri primi, il ritmo col quale si susseguono è irregolare: ad esempio, considerando la decade di interi compresi tra 307 e 317, troviamo quattro numeri primi (307, 311, 313, 317) mentre i successivi quattro primi sono distribuiti, in modo più rarefatto, nell'intervallo tra 317 e 347 (317, 331, 337, 347),cioè in tre decadi.
Spesso, nella scienza, accade che le scoperte più importanti si fanno nel momento in cui si affronta il problema da prospettive diverse e, nel caso dei numeri primi, il cambio di prospettiva arrivò dal grande Gauss, quando, giovanissimo, ricevette in regalo un libro sui logaritmi.
Invece di chiedersi quale è l'n-esimo numero primo, Gauss si domandò quanti primi ci sono tra 1 e N: fino ad allora ci si era focalizzati sul singolo, Gauss si concentrò sull'insieme.
Attraverso una dimostrazione di tipo statistico calcolò una formula approssimata, cioè: N/log(N) (logaritmo naturale in base e=2.718...,numero di Nepero).
Ma si dovette aspettare fino al 1859 per ottenere un significativo passo in avanti verso la comprensione della successione dei numeri primi.
Nel 1859, infatti, Riemann, appena trentaduenne, era già membro dell'Accademia di Berlino: all'epoca, per un giovane matematico, era un punto di arrivo molto ambito. In agosto, Riemann presentò all'Accademia un saggio dal titolo "Sul numero dei primi minori di una certa grandezza" in cui spiegava di aver trovato delle importantissime relazioni tra le funzioni continue a variabili complesse, la somma di serie (in particolare quella di Fourier) e i numeri primi.
In particolare, Riemann ipotizzò che si sarebbe potuto calcolare la posizione dei numeri primi studiando quando una speciale funzione, denominata Zeta di Riemann, si fosse annullata.
In altre parole, l'apparente casualità dei numeri primi può essere generata dalla disposizione allineata degli zeri della funzione complessa Zeta, ma bisogna dimostrare che tali zeri sono effettivamente allineati e a tutt'oggi non esiste tale prova matematica.
Lo stesso Riemann, dopo aver illustrato la sua "congettura", alla fine ammetteva: "Sarebbe auspicabile senza dubbio che si avesse una dimostrazione rigorosa di questa proposizione: tuttavia per il momento ho lasciato questa ricerca da parte dopo qualche breve tentativo infruttuoso, poiché essa mi appare superflua per gli scopi immediati dei miei studi".
Il passo ulteriore è, allo stato attuale, quello di dimostrare l'ipotesi di Riemann (l'ipotesi di Gauss, infatti, è stata dimostrata in modo indipendente da Hadamard e da Vallée-Poussin circa cento anni dopo la formulazione data da Gauss stesso ed è conosciuta, ora, come Teorema dei Numeri Primi (TNP)); tale dimostrazione fornirebbe un metodo in grado di facilitare la scomposizione in fattori primi di un intero che, attualmente, richiede, da un punto di vista computazionale, tempi lunghi.
Sulla difficoltà della fattorizzazione di un numero intero in primi si basano molti sistemi di sicurezza criptati, i quali, se venisse dimostrata la congettura di Riemann, dovrebbero essere modificati (ci sono anche sistemi di crittografia che utilizzano altre tecniche, comunque).
Per concludere questi brevi accenni sull'ipotesi di non-casualità dei numeri primi, vorrei ricordare che, oltre alle ripercussioni in ambito di sicurezza informatica, vi sono altre implicazioni più profonde come, ad esempio, quelle che riguardano la fisica quantistica dei nuclei atomici, la teoria del caos, il calcolo delle probabilità, le sequenze della molecola del DNA, ecc...
Sulla crittografia quantistica e sui computer quantistici avrò modo di scrivere un articolo apposito.
Buona lettura https://img.forumfree.net/html/emoticons/wink.gif

Riemann fu allievo di Dirichlet.
Nel 1837, esattamente cento anni dopo che Eulero dimostrò la sua famosa "formula prodotto" da cui Riemann ricavò la funzione Zeta, Dirichlet riuscì nel suo intento di unificare i concetti dell'aritmetica e dell'analisi, dando inizio alla cosiddetta "teoria analitica dei numeri": la fusione dell'aritmetica con i limiti era compiuta.
Se io sommo ripetutamente, l'uno all'altro, due interi positivi che hanno un fattore comune, ciascun numero risultante avrà lo stesso fattore comune; ad es., prendiamo 6 e 15 e sommiamo ogni volta 6 a 15: avremo 15,21,27,33,39,45,51,ecc..., tutti numeri che hanno 3 come fattore comune.
Facciamo ora la stessa cosa con due interi che non hanno alcun fattore comune, ad esempio 6 e 13: avremo 13, 19, 25, 31, 37, 43, 49,ecc...; ci sono molti numeri primi insieme anche a numeri non primi (come 25 e 49).
Quanti numeri primi ? Infiniti, forse ?
In altre parole, nella sequenza riportata sopra, formata da due interi qualsiasi che non hanno fattori comuni, potrebbero essere contenuti infiniti primi ?
La risposta è sì. Gauss lo aveva intuito e Dirichlet lo dimostrò in un articolo del 1837 intitolato: "Dimostrazione del teorema secondo cui ogni successione aritmetica illimitata, il cui primo membro e differenza sono numeri interi senza fattori comuni, contiene infiniti numeri primi".
Ma la cosa sconcertante è un'altra: supponiamo di avere più sequenze, simili a quella riportata sopra in cui i due interi non hanno fattori comuni, e immaginiamo di proseguire ciascuna sequenza fino ad un certo numero N, grande a piacere; noteremo che non solo ciascuna sequenza contiene infiniti numeri primi ma li contiene anche nella stessa proporzione, ossia pari a circa N/(log N), considerando il Teorema dei Numeri Primi (TNP) vero (ricordate che al tempo di Dirichlet il TNP non era ancora stato dimostrato).
Nella sua dimostrazione Dirichlet utilizzò una forma di aritmetica, sviluppata da Gauss, denominata "aritmetica modulare".
Pensate per un momento alla banale aritmetica dell'orologio. Sostituiamo il 12 sul quadrante con 0, in modo da ottenere le 12 ore dell'orologio formate così: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.
Se sono le otto e aggiungiamo 8 ore, cosa otteniamo ?
Le quattro in punto. Allora in questo tipo di aritmetica avremo 8+8=4 oppure, come si dice matematicamente, 8+8=4 (mod 12) (attenzione: il simbolo = va sostituito con quello di congruenza, formato da 2 lineette con una tilde sopra anziché da 2 lineette soltanto), e si pronuncia "otto più otto è congruo a 4 modulo dodici".
Potrà sembrarvi banale ma l'aritmetica modulare ha implicazioni molto profonde e dà risultati molto strani, a volte.
Gauss ne era un maestro.
Tornando a Dirichlet, egli assimilò molto bene il lavoro di Gauss sulle congruenze e, capitando il risultato di Eulero del 1737 alla sua attenzione, "fuse" le due cose: applicando alcune tecniche di analisi elementare, pervenne alla sua dimostrazione.
Ventidue anni dopo, nel saggio del 1859, Riemann completava la "grande fusione" iniziata da Dirichlet, dischiudendo tutto il campo della teoria analitica dei numeri, che lo avrebbe condotto alla scoperta di quell'oggetto matematico chiamato "funzione Zeta".
Buona lettura https://img.forumfree.net/html/emoticons/wink.gif

P.S. Per approfondimenti vedere:

Formula prodotto di Eulero - Wikipedia
Aritmetica modulare - Wikipedia

Vediamo ora l'importanza dell'aritmetica modulare nella moderna crittografia.
Consideriamo l'insieme formato dalle 21 lettere, ad es. quelle minuscole, dell'alfabeto italiano; a ciascuna lettera dell'insieme sostituisco quella che la segue a tre passi di distanza: cioè ad a sostituisco d, a b sostituisco e, a c sostituisco f e così via.
Otterrò così una tabella di conversione di questo tipo: a--->d - b--->e - c--->f - d--->g - ecc...
In base a questa tabella di conversione, avendo il testo "oggi piove" (testo in chiaro) si potrà codificarlo in "rlln snrbh" (testo cifrato).
Da un punto di vista matematico, ciò equivale a dire che esiste una corrispondenza biunivoca tra gli elementi dell'insieme composto dalle 21 lettere dell'alfabeto italiano in modo tale che a lettere diverse corrispondono lettere diverse.
Sostituiamo ora a ciascuna lettera dell'alfabeto i primi 21 numeri naturali, a partire da 0, creando una corrispondenza biunivoca di questo tipo: a--->0 - b--->1 - c--->2 - d--->3 - ecc...; ripetiamo lo stesso procedimento che abbiamo adottato con le lettere, andando a sostituire a ciascun numero quello che lo segue a tre passi di distanza: avremo così 0--->3 - 1--->4 - 2--->5 - 3--->6 - ecc...
In questo caso il numero 3 è la chiave segreta, ma nessuno impedisce di scegliere un'altra chiave numerica compresa tra 1 e 20 (la chiave 0 non può essere considerata).
Facciamo un esempio: il testo da inviare è "oggi piove" e la chiave segreta è k=4; trasformiamo ora il testo in numeri in base alla tabella di conversione.
Avremo così: "12 6 6 8 13 8 12 19 4". Applichiamo la funzione di codifica, cioè sommiamo 4 (mod 21) a ciascun numero intero del messaggio, ottenendo: "16 10 10 12 17 12 16 2 8".
Chi riceve il messaggio, conoscendo ovviamente la chiave segreta, sarà in grado di decodificarlo tramite la funzione di decodifica: numero-4 (mod 21).
L'inconveniente di questo tipo di codice è che il numero delle chiavi è molto piccolo: chiunque, mediante un metodo esaustivo cosiddetto di "forza bruta", può decodificare il testo semplicemente provando tutte le chiavi, in base ai mezzi di calcolo disponibili (disponendo di un PC, la ricerca esaustiva sarà di molto abbreviata, ovviamente).
Proviamo a rendere le cose un pochino più complicate associando, stavolta, a ciascun numero (da 0 a 20) un altro numero preso a caso, ma non ripetuto, sempre appartenente all'insieme dei ventuno numeri interi, ottenendo, ad esempio: 0--->14 - 1--->6 - 2--->17 - 3--->1 - 4--->7 - ecc...
In definitiva, metto in corrispondenza biunivoca i ventuno numeri 0,1,2,...,20 con una loro permutazione, cioè con un loro particolare ordinamento, ricavando così la chiave che, in questo caso, è la tabella di conversione stessa.
Essendo 21! (ventuno fattoriale) il numero di permutazioni diverse che possiamo ottenere sulle 21 lettere dell'alfabeto, vorrà dire che avremo più di 50 miliardi di miliardi di chiavi: con un computer che elaborasse una chiave ogni microsecondo, occorrerebbero più di un milione di anni per provarle tutte !
Ma anche in questo caso l'euforia finisce presto: con un metodo di tipo "stocastico", cioè probabilistico, basato sulla maggiore o minore frequenza con cui una certa lettera compare in un determinato linguaggio, è possibile "rompere" il codice mono-alfabetico (ad es., in italiano la lettera più frequente è la "a": sapendo che in un testo cifrato il numero 10 appare più frequentemente, posso provare a sostituirlo con la "a", e così via risalendo al messaggio in chiaro).
Un decisivo passo avanti è quello in cui la chiave viene sostituita da un'intera parola-chiave: il codice da mono-alfabetico diventa così poli-alfabetico.
Supponiamo che la parola-chiave segreta (e condivisa soltanto da chi vuole comunicare) sia "cane" e che il messaggio in chiaro sia "oggi piove".
Trasformiamo entrambi in numeri in base alla stessa tabella di conversione riportata sopra: "oggi piove" = 12 6 6 8 13 8 12 19 4 mentre "cane" = 2 0 11 4.
Poniamo la parola-chiave sotto il messaggio e ripetiamola tante volte quanto basta a "ricoprire" l'intero messaggio:
12 6 6 8 13 8 12 19 4
2 0 11 4 2 0 11 4 2
Sommiamo ora (mod 21). Otterremo: 14 6 17 12 15 8 2 2 6.
Tornando alle lettere si avrà la seguente corrispondenza:
o g g i p i o v e
q g t o r i c c g
Ci sono un paio di osservazioni da fare: innanzitutto, come si può notare, ad una stessa lettera del testo in chiaro corrispondono più lettere diverse nel testo cifrato; inoltre, a lettere diverse del testo in chiaro può corrispondere la stessa lettera nel testo cifrato.
E' chiaro che, in questo caso, il metodo statistico non sarà più valido poiché non c'è più relazione tra la frequenza di ripetizione delle lettere nel linguaggio italiano e la frequenza dei simboli nel testo cifrato, come accadeva nel codice mono-alfabetico.
Ma non solo: quanto più lunga è la parola-chiave, tanto più il testo cifrato diventerà casuale, rendendo di fatto vana la ricerca per risalire al messaggio originale.
Al limite, nel caso in cui la parola-chiave fosse lunga quanto il messaggio, ci troveremmo di fronte ad un codice definito "perfetto" (cosa che invece non accade in caso di parola-chiave più corta del messaggio), con una corrispondenza assolutamente casuale tra il testo in chiaro e quello cifrato.
Siamo passati, quindi, da una informazione "deterministica" ad una informazione "caotica", volendo ricordare quanto già scritto sulla "Teoria del Caos".
Solo nel caso in cui una "spia" venisse a conoscenza del testo originale ("oggi piove") potrebbe, per differenza, ricavare la parola-chiave: (testo cifrato) - (testo in chiaro) (mod 21).
Ma allora, perché il codice risulti "inviolabile", è sufficiente cambiare parola-chiave ogni volta che si invia il messaggio.
Un sistema moderno di crittografia molto sicuro è il metodo AES (Advanced Encryption Standard), a patto che la chiave si cambi sempre.
Il problema,semmai, è quello di crittografare la chiave e cioè di trovare una chiave per la chiave, e così via, andando a ritroso all'infinito, cosa certamente non proponibile.
E' possibile, però, "eradicare" il problema alla radice semplicemente rendendo pubbliche le chiavi di cifratura !
Ecco come sono nati i codici crittografici a chiave pubblica.
Buona lettura https://img.forumfree.net/html/emoticons/wink.gif