Fattorizzazione e Test di Primalità con Curve Ellittiche

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