L’elaborato riporta l’analisi teorica e l’implementazione di un test di primalità. Il test in oggetto è una versione del test APR (ideato da Adleman, Pomerance e Rumely) modificata da A.K Lenstra. Il test APR-L si basa sull’utilizzo delle somme di Gauss; la prima parte dell’elaborato è quindi dedicata all’analisi e allo studio dei concetti algebrici utilizzati (residui quadrati, caratteri di Dirichlet, somme di Gauss); sono state quindi analizzate e implementate sia la versione deterministica che la versione probabilistica del test. Il linguaggio utilizzato per l’implementazione è PARI/Gp, un linguaggio creato dall’università di Bordeaux. Infine è analizzata la complessità del test APR-L e vengono confrontati i tempi di esecuzione del programma che implementa la versione deterministica e la versione probabilistica

Somme di Gauss e test di primalità: analisi terorica e implementazione

Adore, Daniela
2011/2012

Abstract

L’elaborato riporta l’analisi teorica e l’implementazione di un test di primalità. Il test in oggetto è una versione del test APR (ideato da Adleman, Pomerance e Rumely) modificata da A.K Lenstra. Il test APR-L si basa sull’utilizzo delle somme di Gauss; la prima parte dell’elaborato è quindi dedicata all’analisi e allo studio dei concetti algebrici utilizzati (residui quadrati, caratteri di Dirichlet, somme di Gauss); sono state quindi analizzate e implementate sia la versione deterministica che la versione probabilistica del test. Il linguaggio utilizzato per l’implementazione è PARI/Gp, un linguaggio creato dall’università di Bordeaux. Infine è analizzata la complessità del test APR-L e vengono confrontati i tempi di esecuzione del programma che implementa la versione deterministica e la versione probabilistica
2011-07-12
65
somme di Gauss, test di primalità
File in questo prodotto:
File Dimensione Formato  
Tesi_AD_586399.pdf

accesso aperto

Dimensione 502.41 kB
Formato Adobe PDF
502.41 kB 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/14787