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

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

Zago, Nicola
2010/2011

Abstract

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
2010-07-13
99
quadratic, sieve, lanczos, blocchi, fattorizzazione,
File in questo prodotto:
File Dimensione Formato  
Tesi.pdf

accesso aperto

Dimensione 1.02 MB
Formato Adobe PDF
1.02 MB Adobe PDF Visualizza/Apri

The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/13514