» Esercizi svolti di Matematica e Fisica

[¯|¯] La crittografia e la legge di distribuzione dei numeri primi

Allo stato attuale delle conoscenze, l'unica espressione analitica della legge di distribuzione dei numeri primi è fornita dalla fomula du Riemann - Von Mangoldt. Qui per "legge di distribuzione" intendiamo una funzione univocamente definita e non ricorsivamente definita, giacché in quest'ultimo caso il costo computazionale sarebbe altissimo.
(altro…)

Posted in Teoria dei numeri | No Comments »

[¯|¯] Crittografia a chiave pubblica e la congettura di Riemann

Crittografia a chiave pubblica

Ipotesi. Bob e Alice sono due amanti che scambiano messaggi utilizzando il sistema crittografico a chiave pubblica RSA. A grandi linee, tale sistema di cirfratura funziona nel seguente modo:

Alice genera un terna ordinata di interi (p,q,e), dove p,q sono numeri primi >100, mentre e < pq è un esponente. La coppia di primi è nota esclusivamente ad Alice, che però rende pubblico e ed n=pq. Tramite un canale pubblico (si pensi agli sms) Bob invia un messaggio m codificato come m^e modulo n. Per decodificare il messaggio, Alice deve eseguire l'operazione (m^e)^d dove d=1/e modulo (p-1)(q-1). Alice può eseguire agevolmente tale operazione poiché è l'unica ad avere accesso a d.

La robustezza dell'algoritmo RSA deriva dal fatto che essendo ignota la funzione di distribuzione dei numeri primi, riesce estremamente costoso dal punto di vista computazionale, fattorizzare numeri interi molto grandi. Viceversa, la conoscenza della predetta distribuzione renderebbe vulnerabile l'algoritmo. Esiste un legame profondo tra la funzione di distribuzione dei primi e gli zeri non banali della funzione zeta di Riemann

La funzione di distribuzione degli zeri della zeta di Riemann

Abbiamo visto nei numeri precedenti che una buona approssimazione della funzione di distribuzione dei numeri primi (f.d.p da qui in poi) è:

Posted in Crittografia, Teoria dei numeri | 1 Comment »