Università Roma Tre

Il concetto di operazione bit tipo somma o sottrazione. Stima del
numero di operazioni bit (tempo macchina) per eseguire le
operazioni fondamentali. Algoritmi che convergono in tempo
esponenziale o polinomiale. Divisibilità. Algoritmo di Euclide,
identità di Bezout e suo tempo di esecuzione. Congruenze.
Teorema cinese dei resti. L'algoritmo dei quadrati successivi.

RSA
L'algoritmo di Adleman, Shamir e Rivest. Formulazione dell'algoritmo
e sua analisi. Attacchi al crittosistema RSA (esponenti di
cifratura e decifratura troppo piccoli, attacco ciclico, attacco del
punto fisso, modulo comune). Richiami sulle congruenze quadratiche e
i simboli di Legendre e Jacobi. Algoritmo polinomiale per il calcolo
del simbolo di Jacobi. Crittosistema di Rabin: descrizione,
sicurezza ed esempi. Distribuzione di Numeri primi. Test di
primalità basati sulla condizione di Fermat. Test di Pocklington.
Pseudo-primalità di Eulero e pseudo-primalità forte. Numeri di
Carmichael: caratterizzazione e prime proprietà. Algoritmi
Montecarlo. Test di Solovay-Strassen. Numeri pseudo--primi forti.
Test di Miller-Rabin. Fattorizzazione di un intero: metodo $\rho$ di
Pollard, metodo p-1 di Pollard, fattorizzazione alla Fermat.

CAMPI FINITI
Fondamenti di teoria dei campi. Costruzione di un campo finito e
sua unicità. Esempi. Polinomi irriducibili e primitivi.
Enumerazione dei polinomi irriducibili e primitivi. Aritmetica in
tempo polinomiale sui campi finiti. Test deterministici di
irriducibilità dei polinomi nei campi finiti. Algoritmo di
Berlekamp per la fattorizzazione di polinomi in un campo finito.

LOGARITMI DISCRETI
Il problema del logaritmo discreto in un gruppo ciclico astratto.
Problema di Diffie Hellman. Scambio di chiavi di Diffie Hellman
sui campi finiti. Crittosistemi di El Gamal e Massey Omura sui
campi finiti. Algoritmi per il calcolo dei logaritmi discreti nei
campi finiti: l' Algoritmo di Shanks, l'Algoritmo di Pohlig -
Hellman ed il Metodo del Calcolo dell'Indice. Schemi di firma
digitale: El-Gamal. Esempi.

A. Languasco - A. Zaccagnini, Introduzione alla crittografia, Hoepli.

W.M. Baldoni -C. Ciliberto - G.M. Piacentini, Aritmetica, crittografia e codici, Springer Verlag.

N. Koblitz, A Course in Number Theory and Cryptography, GTM-Springer.

HANDBOOK OF APPLIED CRYPTOGRAPHY (Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone)