Quadratic sieve e metodo di Lanczos a blocchi nella fattorizzazione di numeri interi

Il Quadratic Sieve è stato il primo algoritmo con complessità sub-esponenziale per la fattorizzazione di numeri interi. Questo è molto importante in quanto rende molto più probabile la rottura di sistemi crittografici la cui sicurezza è basata sulla difficoltà di fattorizzare numeri grandi, come ad esempio RSA. Questa tesi propone la descrizione dell'algoritmo e di tutte le sue varianti comporse nel tempo, confrontandole sullo stesso hardware; un simile confronto non è disponibile in letteratura in quanto i vari raffinamenti sono comparsi nel corso di 15 anni, su macchine molto diverse. Inoltre la tesi tratta di due metodi per la soluzione della fase di algebra lineare dell'algoritmo, in particolare l'eliminazione Gaussiana strutturata e il metodo di Lanczos a blocchi. In particolare quest'ultimo è un metodo euristico che garantisce una migliore complessità sia temporale sia spaziale