Il Problema del Logaritmo Discreto

Nell'ultimo secolo, grazie al rapido sviluppo delle tecnologie informatiche, la matematica ha trovato numerose nuove applicazioni. Lo sviluppo di internet e delle tecnologie di comunicazione hanno portato alla nascita della crittografia, campo dove alcune tecniche matematiche, precedentemente ritenute puramente teoriche, si sono rivelate fondamentali. La nascita della crittografia, l'arte di nascondere i messaggi, risale ad epoca antica. Oggi riveste un'importanza assoluta in molte situazioni, per garantire la sicurezza dei dati personali, dell'invio dei messaggi riservati, e così via. Un sistema crittografico ha come obiettivo quello di celare un messaggio a tutti coloro che sono sprovvisti di particolari informazioni. Per nascondere il significato di un testo si utilizzano operazioni matematiche che siano facili da eseguire ma difficili da invertire in assenza di ulteriori informazioni; tali funzioni vengono dette funzioni unidirezionali. Il problema del logaritmo discreto si basa appunto sulla funzione esponenziale ed è il seguente: dato $y\in G$ bisogna trovare un intero $0 \leq x \leq |G|$ tale che $y = g^x$. Diffie e Hellman nel 1976 descrissero un metodo di scambio delle chiavi crittografico la cui sicurezza dipendeva dalla difficoltà del logaritmo discreto. La congettura di Diffie-Hellman afferma che è computazionalmente molto complicato calcolare $g^{ab}$ dati $g^a$ e $g^b$. Nel Capitolo 1 presenteremo la crittografia e vari sistemi crittografici; introdurremo la crittografia a chiave pubblica e il protocollo di scambio delle chiavi di Diffie e Hellman. Spiegheremo inoltre alcune funzioni unidirezionali. Nel Capitolo 2 presenteremo una serie di risultati algebrici necessari per la comprensione degli argomenti successivamente trattati. Nell'ultima sezione descriveremo in maniera formale il logaritmo discreto e le sue proprietà. Nel Capitolo 3 richiameremo alcune nozioni riguardanti lo studio della complessità computazionale di un algoritmo che verranno poi utilizzate nelle sezioni successive. Illustreremo alcuni dei metodi di \textit{radice quadrata}, così chiamati per via della loro complessità computazionale. Questi metodi non sono particolarmente efficienti ma permettono un graduale approccio al problema. Nel dettaglio analizzeremo i metodi di enumerazione, Baby-step/Giant-step e Pohlig-Hellman. Il problema del logaritmo discreto nel gruppo moltiplicativo dei campi finiti è risolto dall'algoritmo di Shor, trattato nell'ultimo paragrafo, in crittografia quantica. Se fossimo in possesso di un computer quantico, il DLP sarebbe un problema facile da risolvere: di conseguenze la moderna crittografia non adotta tale protocollo come sistema su cui basare i moderni sistemi crittografici.