Ebook: Aritmetica, crittografia e codici

Il volume potrà essere utile ai docenti che intendano svolgere un corso su questi argomenti, la cui presenza sempre più viene richiesta nei corsi di laurea di matematica, fisica, informatica, ingnegneria.

Table of Contents

Cover

Aritmetica, crittografia e codici

ISBN 10 8847004551 ISBN 13 9788847004559

Introduzione

Indice

1 Qualche richiamo sui numeri

1.1 Principio di induzione completa
1.2 Il concetto di ricorsivit�
1.2.1 I numeri di Fibonacci
1.2.2 Altri esempi di dinamica di popolazioni
1.2.3 La torre di Hanoi: un caso lineare non omogeneo
1.3 L'algoritmo di Euclide
1.3.1 La divisione
1.3.2 Il massimo comun divisore
1.3.3 L'identit� di B�zout
1.3.4 Equazioni lineari diofantee
1.3.5 Anelli euclidei
1.3.6 Polinomi
1.4 Contare in basi diverse
1.4.1 La rappresentazione posizionale dei numeri
1.4.2 La base 2
1.4.3 Le quattro operazioni in base 2
1.4.4 Numeri interi in base qualunque
1.4.5 Rappresentazione dei numeri reali in base qualunque
1.5 Frazioni continue
1.5.1 Frazioni continue semplici finite e numeri razionali
1.5.2 Frazioni continue semplici infinite e numeri irrazionali
1.5.3 Frazioni continue periodiche
1.5.4 Modello geometrico delle frazioni continue
1.5.5 L'approssimazione di irrazionali mediante i convergenti
1.5.6 Frazioni continue ed equazioni diofantee

2 Complessit� computazionale

2.1 Il concetto di complessit� computazionale
2.2 Il simbolo O
2.3 Tempo polinomiale, tempo esponenziale
2.4 Complessit� delle operazioni elementari
2.5 Algoritmi e complessit�
2.5.1 Complessit� dell'algoritmo di Euclide
2.5.2 Dalla scrittura binaria a quella decimale: complessit�
2.5.3 Complessit� delle operazioni tra polinomi
2.5.4 Un algoritmo pi� efficiente per la moltiplicazione
2.5.5 Metodo di Ruffini-Horner

3 Dall'infinito al finito

3.1 Congruenze: prime propriet�
3.2 Prime applicazioni delle congruenze
3.2.1 La prova del nove
3.2.2 Criteri di divisibilit�
3.3 Congruenze lineari
3.3.1 Potenze modulo n
3.4 Il Teorema cinese dei resti
3.5 Esempi
3.5.1 Il calendario perpetuo
3.5.2 Girone all'italiana

4 Finito non basta: problemi di fattorizzazione

4.1 Numeri primi
4.1.1 Il Teorema Fondamentale dell'Aritmetica
4.1.2 Distribuzione dei numeri primi
4.1.3 Il crivello di Eratostene
4.2 Numeri primi e congruenze
4.2.1 Il calcolo della funzione di Eulero
4.2.2 Il Piccolo Teorema di Fermat
4.2.3 Il teorema di Wilson
4.3 Rappresentazione in base qualunque dei numeri razionali
4.4 Primi di Fermat, primi di Mersenne e numeri perfetti
4.4.1 Fattorizzazione di interi della forma bn � 1
4.4.2 Numeri primi di Fermat
4.4.3 Numeri primi di Mersenne
4.4.4 Numeri perfetti
4.5 Fattorizzazione in un dominio di integrit�
4.5.1 Elementi primi e irriducibili in un anello
4.5.2 Domini fattoriali
4.5.3 Anelli noetheriani
4.5.4 Fattorizzazione di polinomi su un campo
4.5.5 Fattorizzazione di polinomi su un anello fattoriale
4.5.6 Polinomi a coefficienti razionali o interi
4.6 L'interpolazione di Lagrange e applicazioni
4.7 Il metodo di fattorizzazione di Kronecker

5 Campi finiti e congruenze polinomiali

5.1 Un po' di teoria dei campi
5.1.1 Estensioni di campi
5.1.2 Estensioni algebriche
5.1.3 Campo di riducibilit� completa di un polinomio
5.1.4 Radici dell'unit�
5.1.5 Chiusura algebrica
5.1.6 Campi finiti e loro sottocampi
5.1.7 Automorfism dei campi finiti
5.1.8 Polinomi irriducibili su Zp
5.1.9 Campo F4 di ordine quattro
5.1.10 Campo F8 di ordine otto
5.1.11 Campo F16 di ordine sedici
5.1.12 Campo F9 di ordine nove
5.1.13 Sui generatori di un campo finito
5.1.14 Complessit� del calcolo in un campo finito
5.2 Congruenze polinomiali non lineari
5.2.1 Equazioni di secondo grado
5.2.2 Residui quadratici
5.2.3 Il simbolo di Legendre e sue propriet�
5.2.4 La legge di reciprocit� quadratica
5.2.5 Il simbolo di Jacobi
5.2.6 Un algoritmo per il calcolo delle radici quadrate

6 Test di primalit� e di fattorizzazione

6.1 Numeri pseudoprimi e test probabilistici
6.1.1 Numeri pseudoprimi
6.1.2 Test probabilistici e test deterministici
6.1.3 Un primo test di primalit� probabilistico
6.1.4 Numeri di Carmichael
6.1.5 Pseudoprimi di Eulero
6.1.6 Il test probabilistico di primalit� di Solovay-Strassen
6.1.7 Pseudoprimi forti
6.1.8 Test probabilistico di primalit� di Miller-Rabin
6.2 Radici primitive
6.2.1 Radici primitive e indice
6.2.2 Ancora sul test di Miller-Rabin
6.3 Un test di primalit� deterministico polinomiale
6.4 Metodi di fattorizzazione
6.4.1 Il metodo di fattorizzazione di Fermat
6.4.2 Generalizzazione del metodo fattorizzazione di Fermat
6.4.3 Il metodo delle basi di fattorizzazione
6.4.4 Fattorizzazione e frazioni continue
6.4.5 L'algoritmo del crivello quadratico
6.4.6 Il metodo
6.4.7 Variazione del metodo

7 Segreti... e bugie

7.1 I cifrari classici
7.1.1 Le prime scritture segrete nella storia
7.2 L'analisi del testo cifrato
7.2.1 Macchinari per cifrare
7.3 Impostazione matematica di un crittosistema
7.4 Alcuni cifrari classici basati sull'aritmetica modulare
7.4.1 Cifrari affini
7.4.2 Cifrari con matrici o di Hill
7.5 L'idea di base della crittografi a chiave pubblica
7.5.1 Un algoritmo per il calcolo dei logaritmi discreti
7.6 Problema dello zaino e applicazioni alla crittografi
7.6.1 Cifrario a chiave pubblica basato sul problema dello zaino o di Merkle-Hellman
7.7 Il sistema RSA
7.7.1 Accesso al sistema RSA
7.7.2 Invio di un messaggio cifrato con il sistema RSA
7.7.3 Decifratura di un messaggio cifrato con il sistema RSA
7.7.4 Perch� ha funzionato?
7.7.5 Autenticazione delle firm con il sistema RSA
7.7.6 Un commento sulla sicurezza del sistema RSA
7.8 Varianti del sistema RSA e oltre
7.8.1 Scambio di chiavi private
7.8.2 Il crittosistema di Elgamal
7.8.3 Zero-knowledge proof: ovvero convincere che si conosce un risultato senza svelarne il contenuto o la dimostrazione
7.8.4 Nota storica
7.9 Crittografi e curve ellittiche
7.9.1 Crittografi in un gruppo
7.9.2 Curve algebriche in un piano affine numerico
7.9.3 Rette e curve razionali
7.9.4 Curve iperellittiche
7.9.5 Curve ellittiche
7.9.6 Legge di gruppo sulle curve ellittiche
7.9.7 Curve ellittiche su R, C e Q
7.9.8 Curve ellittiche su campi finiti
7.9.9 Curve ellittiche e crittografi
7.9.10 Il metodo di fattorizzazione p 1 di Pollard

8 Trasmettere senza. . . paura di sbagliare

8.1 Auguri di buon compleanno!
8.2 Fotografando nello spazio o lanciando monete, arriviamo ai codici
8.3 Codici che correggono gli errori
8.4 Limitazioni sugli invarianti
8.5 Codici lineari
8.6 Codici ciclici
8.7 Codici di Goppa

9 Il futuro � gi� presente: la crittografia quantistica

9.1 Una prima incursione nel mondo quantistico: l'esperimento di Young
9.2 Il computer quantistico
9.3 Il cifrario di Vernam
9.4 Un breve glossario di meccanica quantistica
9.5 Crittografi quantistica

10 Soluzione di alcuni esercizi

10.1 Esercizi del Capitolo 1
10.2 Esercizi del Capitolo 2
10.3 Esercizi del Capitolo 3
10.4 Esercizi del Capitolo 4
10.5 Esercizi del Capitolo 5
10.6 Esercizi del Capitolo 6
10.7 Esercizi del Capitolo 7
10.8 Esercizi del Capitolo 8
10.9 Esercizi del Capitolo 9

Riferimenti bibliografici

Indice analitico