Il sito e' under construction
<br>
Il corso comincera' il giorno 20 settembre 2021 secondo 
l'orario previsto dalla Facolta' di Ingegneria (LUN ore 11.30-13.15, aula 12 e VEN ore 11.30-13.15 aula B9).<br>
 Vedi anche <a href="https://didatticaweb.uniroma2.it/it/informazioni/index/insegnamento/196097-Teoria-Elementare-Dei-Numeri/16297"> 
la pagina del corso su DidatticaWeb </a>

<br><span><br>
PROGRAMMA
<br><span><br>

In breve, il corso riguarda alcuni algoritmi riguardanti numeri interi: test di primalita', fattorizzazione in primi, calcolo del logaritmo discreto.
<br><br>
MOTIVAZIONE.
<br> 
Breve presentazione di alcuni metodi crittografici: RSA, scambio di chiavi (DIffie-Hellman, El Gamal..).
<br><br>
PRELIMINARI DI ARITMETICA e ALGEBRA.
<br>
Richiami dal Corso Algebra e Logica (Laurea Triennale in Ingegneria Informatica, primo anno):<br> 
Divisione con resto, congruenza modulo n, l'anello Z(n), il gruppo Z(n)* degli elementi di Z(n) invertibili rispetto alla moltiplicazione. 
Funzione Phi di Eulero. Algoritmo euclideo.<br>
Ordine di un elemento in un gruppo, teorema di Lagrange, teoremi di Fermat ed Eulero.<br>
Teorema cinese dei resti, formula per la funzione phi di Eulero.
<br><br>
GRUPPI
<br>
Gruppi ciclici. Struttura di gruppi abeliani finiti. Teorema della radice primitiva: se n e' la potenza di un numero primo allora il gruppo Z(n)* e' ciclico
<br><br>
COMPLESSITA'
<br>
Stima della complessita' di varie operazioni elementari: divisione con resto, algoritmo euclideo per il calcolo dell'MCD, scrittura in base b,
 somma, moltiplicazione, potenza , inverso modulo n. Complessita' polinomiale, esponenziale, subesponenziale
<br><br>
TEST DI PRIMALITA'
 <br>
Fermat, Miller-Rabin, Numeri di CarmIchael, stima dell probabilita' di riuscita e della complessita'. 
<br><br>
ALCUNI ALGORITMI DI FATTORIZZAZIONE
<br>
Teorema dei numeri primi (senza dimostrazione), Pollard rho, Pollard p-1, Fermat, crivello quadratico. Stima delle vare complessita' probabilistiche: 
funzione di Dickman.<br>
Curve ellittiche e il metodo delle curve ellittiche (ECM).
<br><br>
ALCUNI ALGORITMI PER IL LOGARITMO DISCRETO
<br>
Baby step-giant step. Calcolo dell’indice (e altri)
<br><span><br>
MATERIALE DIDATTICO:
 <br> Testo delle lezioni, note a cura dei Proff. Geatti e Schoof, libro: N. Koblitz, A Course in Number Theory and Cryptography (second edition), Springer 
<br><span><br>
MODALITA' D'ESAME
<br>
In due parti.  Un  compito scritto sulle nozioni base del corso e, se si consegue un voto sufficiente allo scritto,  un progetto consistente nell'implementare uno degli algoritmi un po' piu' complicati del corso (crivello quadratico, ECM, calcolo dell'indice..)
 in un programma atto a risolvere il problema dato (fattorizzazione, logaritmo discreto) in un concreto range di numeri interi