Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Fattorizzazione e Test di Primalità con Curve Ellittiche

A seguito di un capitolo introduttivo sulle proprietà generali delle curve ellittiche, la presente Tesi si concentra sull'applicazione delle stesse nei problemi della primalità e della fattorizzazione dei numeri interi.

Vengono esposti i classici:

- Metodo "p-1" di Pollard (algoritmo di fattorizzazione probabilstico);
- Test di Pocklington-Lehmer (test di primalità probabilistico di tipo Las Vegas);
- Test di Solovay-Strassen e di Miller-Rabin (test di (pseudo)primalità probabilistici di tipo Monte Carlo).

Vengono analizzati in dettaglio i Metodi con le curve ellittiche:

- "ECM" (Elliptic Curve Method) di H. Lenstra (generalizzazione del Metodo di Pollard);
- "ECPP" (Elliptic Curve Primality Proving) di S. Goldwasser e J. Kilian (generalizzazione del Test di Pocklington-Lehmer).

Viene inoltre presentato un esempio di applicazione di tali problemi nel campo della crittografia, esibendo un analogo di crittosistema RSA con curve ellittiche.

Mostra/Nascondi contenuto.
Introduzione Il problema della fattorizzazione di un numero intero e un problema che ha sempre aascinato i matematici di ogni epoca, da Eratostene (III sec. a.C.) a Fermat (1601-1665) ed Eulero (1707-1783), no ai nostri giorni. Fattorizzare un intero signica non soltanto partizionarlo come prodotto di altri numeri interi minori (in questo caso la partizione non sarebbe unica), ma scomporlo nei suoi fattori primi. Il Teorema Fondamentale dell’Aritmetica in questo caso ci assicura l’esistenza e l’unicit a della scomposizione: Un intero n 2 o e primo o potenza di un primo, o si pu o rappresentare in modo unico (a meno dell’ordine) come prodotto di primi o potenze di primi distinti. Saper ridurre un numero intero in fattori primi e essenziale se si lavora nella teoria dei numeri, ma non solo. Per esempio, capire quando un intero n e esprimibile come somma di due quadrati, calcolare l’ordine del gruppo molti- plicativo delle unit a di Z=nZ, o trovare un’espressione per una certa funzione aritmetica, sono problematiche facilmente risolvibili non appena si conosca la fattorizzazione in primi di n. Con numero \composto" intenderemo un numero intero non primo, che e cio e la potenza di un primo oppure il prodotto di potenze di almeno due primi. Un processo di fattorizzazione di un dato intero e costituito da due passi principali. In primo luogo occorre stabilire se il numero e primo o com- posto, e lo si fa applicando ad esso un test di primalit a . Una volta stabilito che il numero dato e composto, occorre trovare un suo fattore non banale tramite un algoritmo di fattorizzazione. Una completa decomposizione in fattori primi e ottenuta applicando ricorsivamente questi due algoritmi. Da qualche decennio la considerazione verso il problema della primalit a e della fattorizzazione e decisamente aumentata, da un lato grazie all’utilizzo di strumenti matematici sempre pi u sosticati rispetto a quelli usati preceden- temente, come ad esempio le curve ellittiche, dall’altro grazie alla possibilit a, sempre pi u realizzata, di applicare la teoria dei numeri non solo in altri campi della matematica, ma anche in ambiti pratici. Si pensi all’importanza della iv

Laurea liv.II (specialistica)

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Gabriele Pulvano Contatta »

Composta da 97 pagine.

 

Questa tesi ha raggiunto 1091 click dal 27/05/2011.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.