Nota degli Autori
Legenda

1 Equazioni e Aritmetica
1.1 Equazioni e poligoni regolari
1.1.1 Radici quadrate
1.2 Il gruppo ciclico delle classi di resto modulo n
1.3 Gruppi: Definizioni e Teoremi fondamentali
1.3.1 Omomorfismi ed isomorfismi
1.3.2 Prodotti diretti

2 Le congruenze
2.1 Aritmetica modulo n
2.1.1 Proprieta' delle congruenze
2.2 L'algoritmo di Euclide
2.3 Anelli: Definizioni e Teoremi fondamentali

3 Proprieta' aritmetiche dei numeri primi
3.1 Definizioni e prime proprieta'
3.2 Il Teorema di Fermat e le sue conseguenze
3.3 Il Teorema di Gauss
3.3.1 Applicazione: numeri pseudocasuali
3.3.2 Problemi
3.4 Pseudoprimi e numeri di Carmichael
3.5 La funzione di Eulero
3.6 Dimostrazione del Teorema di Gauss
3.7 La legge di reciprocita' quadratica
3.8 Altre condizioni necessarie per la primalita'
3.8.1 Pseudoprimalita' di Eulero
3.8.2 Pseudoprimalita' forte
3.8.3 Verifica della primalita' in insiemi finiti

4 Campi
4.1 Definizioni generali
4.2 Come costruire campi finiti
4.3 Costruzione dei campi con 4 ed 8 elementi
4.4 Costruzione del campo con 27 elementi
4.5 Campi finiti
4.6 Un campo particolarmente interessante
4.7 Campi algebricamente chiusi
4.7.1 Formula dell'equazione di secondo grado

5 Crittografia
5.1 Introduzione
5.2 Crittosistema
5.3 Cenni storici
5.4 Teoria di Shannon
5.4.1 Cifrario perfetto (one-time pad)
5.5 Crittanalisi: cenni
5.6 Crittografia classica
5.6.1 Crittosistemi a pacchetto
5.6.2 Crittosistemi a flusso
5.6.3 Crittosistemi affini
5.6.4 Crittosistema Feistel
5.6.5 DES (Data Encryption Standard)
5.6.6 AES (Rijndael)
5.7 Crittografia a chiave pubblica
5.8 Lo scambio di chiavi nel crittosistema di Diffie ed Hellman
5.9 Il crittosistema RSA di Rivest, Shamir e Adleman
5.9.1 Attacchi a RSA
5.9.2 Attacchi all'implementazione di RSA
5.9.3 Esempio pratico di codifica con RSA
5.10 Il crittosistema di Rabin
5.10.1 Sicurezza del sistema Rabin
5.11 Il crittosistema di ElGamal
5.12 Il crittosistema di Massey-Omura
5.13 Firma digitale
5.13.1 Schema generale di firma digitale
5.13.2 Firma digitale: certificazione dell'identita' con RSA
5.13.3 Firma digitale: certificazione dell'identita' con ElGamal
5.14 Vantaggi della Crittografia a chiave pubblica
5.15 Crittografia e curve ellittiche

6 Algoritmi
6.1 Aritmetica in base b e complessita' computazionale
6.1.1 Numeri in base b
6.1.2 Operazioni elementari e complessita' della somma di interi
6.1.3 Complessita' del prodotto di interi
6.1.4 Cambiamento di base e radice quadrata intera binaria
6.2 L'Algoritmo di Euclide
6.2.1 Complessita' dell'Algoritmo di Euclide
6.2.2 Soluzione dei sistemi di congruenze lineari
6.3 Il crivello di Eratostene
6.4 Criteri di primalita'
6.4.1 Certificati di primalita' succinti
6.5 Fattorizzazione: algoritmi esponenziali
6.5.1 Divisione per tentativi
6.5.2 Fattorizzazione "alla Fermat" (algoritmo di Lehman)
6.5.3 Fattorizzazione e crivello
6.5.4 Il metodo p di Pollard
6.5.5 Metodo p- 1 di Pollard
6.6 Fattorizzazione: algoritmi subesponenziali
6.6.1 Il crivello quadratico di Pomerance
6.6.2 Esempio numerico
6.6.3 Il crivello con i campi di numeri
6.7 Ricerca di un generatore nei campi finiti
6.8 Logaritmo discreto
6.8.1 L'algoritmo di Shanks: baby steps, giant steps
6.9 Algoritmi ausiliari
6.9.1 Calcolo di prodotti modulo n
6.9.2 Calcolo di potenze modulo n
6.9.3 Calcolo di potenze di polinomi modulo un polinomio e modulo n
6.9.4 L'algoritmo della divisione con resto

7 Alcuni protocolli crittografici
7.1 Introduzione
7.2 Protocolli di base
7.2.1 Scambio delle chiavi
7.2.2 Autenticazione
7.2.3 Secret splitting
7.2.4 Secret sharing
7.2.5 Secret broadcasting
7.3 Protocolli intermedi
7.3.1 Marcatura temporale di un documento (timestamping)
7.3.2 Canali subliminali
7.3.3 Firma di gruppo
7.3.4 Testa o croce?
7.3.5 Poker mentale
7.3.6 Bit commitment
7.4 Protocolli avanzati
7.4.1 Dimostrazioni a conoscenza nulla
7.4.2 Identificazione e conoscenza nulla
7.4.3 Firma cieca
7.4.4 ANDOS
7.4.5 Trasferimento privo di memoria (oblivious transfer)
7.4.6 Firma simultanea
7.4.7 Posta certificata
7.4.8 Elezioni elettroniche
7.4.9 Cena dei crittografi
7.4.10 Denaro elettronico
8 Distribuzione dei numeri primi
8.1 Euristica
8.2 Risultati quantitativi
8.3 Numeri senza fattori primi grandi
8.4 Formule per i numeri primi
8.5 Pseudoprimi e numeri di Carmichael

9 Introduzione a PARI/Gp
9.1 Introduzione
9.2 Alcuni strumenti di calcolo
9.3 Primi passi con PARI/Gp
9.3.1 Documentazione
9.3.2 Primi passi
9.3.3 Help in PARI/Gp
9.4 Programmare in PARI/Gp: alcuni comandi di base
9.4.1 Leggere un file
9.4.2 Argomenti di funzioni e loro passaggio
9.4.3 Variabili locali
9.4.4 Come inserire i dati
9.4.5 Scrivere in un file
9.5 Alcune famose asserzioni sui primi
9.6 Esempi in PARI/Gp
9.6.1 Distribuzione dei primi
9.6.2 Calcoli riguardanti RSA in PARI/Gp
9.6.3 Alcuni esempi in PARI/Gp
9.6.4 Alcuni esercizi

10 Letture ulteriori

A Complementi
A.1 Classi di complessita' dei problemi di decisione
A.1.1 La classe P
A.1.2 La classe NP
A.1.3 Problemi NP-completi
A.1.4 Altre classi: BPP, RP, ZPP
A.1.5 Relazioni tra le classi
A.2 Il principio dei cassetti
A.3 Funzioni aritmetiche
A.4 Relazioni di equivalenza
A.5 La Notazione di Bachmann-Landau
A.6 La Formula di Stirling
A.7 Il paradosso dei compleanni
A.8 Frazioni continue
A.9 Alcuni cenni di Algebra lineare
A.9.1 Matrici
A.9.2 Determinante di una matrice
A.9.3 Matrici elementari

Bibliografia
Indice analitico