Tesi di LAUREA SPECIALISTICA Titolo Metodi di fattorizzazione per la crittografia Data 2011-10-04 Autore/i Andreoli, Tommaso Relatore Betti, R. Full text non disponibile Abstract Il problema che riguarda la decomposizione di un numero intero nei suoi fattori primi - il cosiddetto problema di fattorizzazione degli interi - ha impegnato numerose fra le menti più brillanti della matematica di ogni epoca, a partire dall’antica Grecia, per giungere fino ai giorni nostri come quesito ancora aperto a soluzioni che possano presentare un maggior grado di efficienza in termini di tempo di esecuzione. A dispetto della sua apparente semplicità, la fattorizzazione cela, infatti, dietro di sé una sfida tanto affascinante quanto complessa, in cui confluiscono, sino a congiungersi, le idee di matematici esperti nella teoria dei numeri e di luminari di altre discipline tecnico-scientifiche, prima fra tutte l’informatica teorica. E proprio in ragione di questa difficoltà intrinseca al problema della fattorizzazione di interi che è stato possibile costruire, dagli anni ’70 del secolo scorso, un nuovo modo di fare crittografia. L’elevato tempo di computazione richiesto per poter decomporre in primi numeri di grosse dimensioni ha fatto sì che, su tale problema, potesse essere riposta gran parte della sicurezza legata alla trasmissione di informazioni considerate riservate. Oggi molti dei crittosistemi in uso detti a chiave pubblica – tra i quali si annovera il più celebre e impiegato sistema RSA – si affidano all’impossibilità di riuscire in tempi ragionevolmente brevi a ridurre in fattori primi numeri interi che si compongono di qualche centinaio di cifre decimali. Il seguente lavoro si prefigge come obiettivo quello di fornire una panoramica generale sulle tecniche algoritmiche di fattorizzazione più utilizzate nella pratica crittografica, descrivendone idee di base e schemi di procedimento, e illustrando poi, per ciascuna di tali tecniche, i principali punti di forza e di debolezza legati ai tempi di computazione. Pertanto, il tutto viene a proporsi come un primo punto di riferimento per il lettore interessato a scoprire, in modo sufficientemente dettagliato, la teoria sottostante, i pregi e i difetti legati alle più importanti tecniche di fattorizzazione finora conosciute.