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 probabilisticaFile | 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
https://hdl.handle.net/20.500.12608/14787