|
|
|
Diario delle lezioni
Alla fine di ogni lezione vengono indicati i riferimenti agli appunti
([Chen]), al libro
"A course in number Theory and Cryptography"
([Kob]),
al libro "Theory of Numbers"
([Ste]),
al libro "Introduction to Analytic Number Theory"
([Apo]),
agli appunti online "Introduzione alla teoria analitica dei numeri"
([Zac]),
e agli altri
eventuali testi suggeriti,
i cui riferimenti precisi trovate nella sezione dei
testi consigliati.
1) Martedì 2 ottobre (lezioni 1-2):
[Kob] Capitolo 1.1
2) Giovedì 4 ottobre (lezioni 3-4):
Operazioni bit. Limitazioni superiori per il numero di operazioni bit
richieste dalla somma, prodotto quoziente di due numeri, per la conversione
da una base alla base 2;
nel calcolo del binomiale, del prodotto di polinomi, nella conversione tra
basi. Esempi di divisione in base 2.
Primi esercizi dalla
Scheda 1.
[Kob] Capitolo 1.1
3) Venerdì 5 ottobre (lezioni 5-6):
Naturali, pricipio di induzione e buon ordinamento, divisione euclidea,
divisibilità massimo comune divisore: esistenza e unicità.
Algoritmo di
Euclide e sua complessità computazionale.
Unità Numeri primi e composti.
[Kob] Capitolo 1.1
[Chen] Chapter 1
4) Martedì 9 ottobre (lezioni 7-8):
Theorem 1.4 (Chen). Lemma fondamentale: se un primo
divide un prodotto, allora divide almeno uno dei fattori.
Teorema fondamentale
dell'aritmetica (fattorizzazione unica in primi), esistenza di infiniti primi.
Parte intera [n] di un intero
e sue proprietà. Massima potenza di un primo che divide un
naturale. Proposizione: il massimo esponente di p primo che divide n!
si calcola come la somma di [n/p^j], per ogni j naturale positivo.
Esercizi 1-10 della
Scheda 1.
[Chen] Chapter 1
[Ste]
Capitolo 6 (tutto), capitolo 7.4, capitolo 9.1, 9.2
5) Giovedì 11 ottobre (lezioni 9-10):
Questioni sui primi: come fare una lista dei primi fino a n?
Come determinare se un intero fino a n è primo o composto? Ci
sono infiniti primi? Esiste una formula per l'ennesimo primo?
Un polinomio che valutato negli interi dia sempre un primo?
Esistono infiniti primi gemelli?
Primi gemelli, primi cugini, primi sexy, triplette di primi, costellazioni
di primi. La congettura di De Polignac. Ci sono successioni di interi
consecutivi composti che sia di lunghezza arbitraria?
Il crivello di
Eratostene. La funzione PiGreco(n)= numero di primi fino a n. Il motore di
ricerca di successioni intere:
Online Encyclopedia of integer sequences.
Un poco di storia di teoria computazionale dei numeri.
I primi 1
di Mersenne.
Great Internet Mersenne Prime Search.
[Ste]
Capitolo 9.3, 9.4
6) Venerdì 12 ottobre (lezioni 11-12):
Diverse dimostrazioni sull'esistenza dei numeri primi (dim 1 usa p!+1,
dim 2 usa l'esistenza di infiniti primi nella successione 6X-1, dim 3 usa
i numeri di Fermat generalizzati. Proposizione: esistono successioni di
interi consecutivi composti di lunghezza arbitraria. Proposizione:
per ogni
polinomio f(x) a coefficienti interi, esistono infiniti valori s per
cui f(s) è composto.
Iniziare gli esercizi della
Scheda 2.
[Ste]
Capitolo 9.3, 9.4 e relativi esercizi.
7) Martedì 16 ottobre (lezioni 13-14):
Funzioni aritmetiche.
La funzione tau(n) (o d(n)) che conta il numero di divisori di n,
formula per tau. La funzione sigma(n) somma dei divisori di n, e calcolo
della
sua formula in funzione della fattorizzazione standard.
Queste due funzionisono moltiplicative.
Numeri perfetti: sigma(n)=2n, deficienti e abbondanti.
Determinazione dei numeri perfetti pari, che sono della forma
2^(k-1)(2^k-1), con k primo, (2^k-1) primo di Mersenne.
Funzioni aritmetiche moltiplicative.
Costruzione di nuove funzioni moltiplicative da funzioni moltiplicative
note: F(n) = somma f(d), somma estesa ai divisori di n.
Le funzioni sigma e tau come funzioni moltiplicative.
[Ste]
Capitolo 10.1, 10.2 e 10.3., 11.1, 11.2
8) Giovedì 18 ottobre (lezioni 15-16):
Costruzione di nuove funzioni moltiplicative da funzioni
moltiplicative note: F(n) = somma f(d), somma estesa ai divisori di n.
Le funzioni sigma e tau come funzioni moltiplicative.
Equazioni diofantee di primo grado. Caratterizzazione delle equazioni
ax+by=n
che ammettono soluzioni, scrittura di tutte le soluzioni in forma
parametrica. Soluzioni positive.
Esercizi dalla
Scheda 1. e
Scheda 2.
[Ste]
Capitolo 11.2 e 15.1
9) Venerdì 19 ottobre (lezioni 17-18):
Terne pitagoriche, ovvero: la ricerca di tutte le soluzioni
dell'equazione x^2+y^2=z^2. Terne primitive. Caratterizzazione
delle terne pitagoriche primitive nella forma
(2uv,u^2-v^2, u^2+v^2)
al variare di 0 < v < u naturali coprimi e con parità diversa.
Esercizi dalla
Scheda 3.
[Ste]
Capitolo 23.1
10) Martedì 23 ottobre (lezioni 19-20):
Stime asintotiche e valor medio per le funzioni tau (numero dei divisori).
Stime asintotiche per la funzione sigma (somma dei divisori).
La costante gamma di Eulero Mascheroni.
La funzione aritmetica di Möbius. Sua relazione con la funzione
zeta di Riemann.
La funzione di Möbius è moltiplicativa.
[Chen]
Capitolo 2.1 e 2.2
11) Giovedì 25 ottobre (lezioni 21-22):
Proposizione: L'ultimo teorema di Fermat è equivalente al
seguente: per ogni
p primo dispari o p=4, l'equazione diofantea x^p+y^p=z^p non ha soluzioni
La somma dei suoi valori estesa ai
divisori di n vale 1 se n = 1 vale 0 altrimenti. La formula di inversione
di
Möbius. Espressione esplicita.
Funzione Phi di Eulero ("totient function"). Relazione tra la funzione di
Möbius e di Eulero. Formula per Phi e alcune sue proprietà.
Esercizi dalle Schede 3. e 4.
[Apo]
Capitolo 2.1 e 2.2
[Chen]
Capitolo 2.3
12) Venerdì 26 ottobre (lezioni 23-24):
Funzione Phi di Eulero ("totient function"). Relazione tra la funzione di
Möbius e di Eulero. Formula per Phi e alcune sue proprietà.
Il prodotto di convoluzione (di Dirichlet)
di funzioni aritmetiche, e sue proprietà (associativo, commutativo,
esistenza dell'elemento neutro).
Esistenza dell'inverso di f per la convoluzione sotto le ipotesi
che f(1) sia non nullo: formula per ricorrenza.
Le funzioni moltiplicative con f(1) non nullo formano gruppo rispetto
alla convoluzione.
[Apo]
Capitolo 2.3, 2.4, 2.5, 2.6.
[Chen]
Capitolo 2.4, 2.5
/) Martedì 30 ottobre (lezioni /): Lezione cancellata dal rettore per maltempo.
13) Mercoledì 31 ottobre (lezioni 25-26):
Funzione aritmetica di Mangoldt e sue proprietà.
Valore medio asintotico della funzione Phi di Eulero.
Richiami sulle congruenze. Sistemi di residui completi e ridotti.
[Apo]
Capitolo 2.3, 2.4, 2.5, 2.6, 2.7
[Chen]
Capitolo 2.4, 2.5
14) Martedì 6 novembre (lezioni 27-28):
Teorema di Lagrange: Un'equazione polinomiale di grado n con coefficiente
direttivo non multiplo di p ammette al più n soluzioni se p è
primo.
Conseguenze: Teorema: un polinomio di grado n che abbia più di n
soluzioni modulo un primo ha tutti i coefficienti multipli di p (Analogo del
principio di identità polinomiale sui complessi).. Corollario
(teorema di Wilson): (p-1)! congruo a (-1) modulo p se p è
primo.
Le funzioni simmetriche. Funzioni simmetriche elementari.
Funzioni simmetriche omogenee e somme di potenze (le "power sum").
Teorema di Wolstenholme: se p è un primo da 5 in poi, allora
la somma dei termini (p-1)!/k, per k da 1 a (p-1) è
congrua a 0 modulo p^2.
[Apo]
Capitolo 5.5
15) Giovedì 8 novembre (lezioni 29-30):
Sistemi di congruenze lineari. Teorema cinese dei resti e sua generalizzazione.
Teorema (riduzione da modulo m a modulo pi^ai): se m_i sono dei positivi a due
a due coprimi per i=1,...r, ed m è il prodotto degli m_i, allora
f(x) congruo 0 (mod m) ammette soluzione se e solo se ogni congruenza
f(x) congruo 0 (mod m_i) per ogni i. Inoltre se v(m) e v(m_i) rappresentano il
numero di soluzioni delle relative congruenze, allora v(m)=v(m_1)...v(m_r).
[Chen]
Capitolo 3.4 e 3.5
[Apo]
Capitolo 5.5, 5.6, 5.7 e 5.8
16) Venerdì 9 novembre (lezioni 31-32):
Teorema di Euler-Fermat. Piccolo Teorema di Fermat.
Equazioni alle congruenze. Numero di soluzioni delle congruenze.
Congruenze lineari: condizioni necessarie e sufficienti per avere soluzioni.
Congruenze polinomiali: problemi connessi.
Riduzione di una congruenza polinomiale (mod p^s) a una congruenza
(mod p^(s-1)):
"sollevamento" delle soluzioni. Un esempio:
risoluzione completa di una congruenza
polinomiale.
[Chen]
Capitolo 3.1 e 3.2.
[Ste]
Capitolo 13, 14 e 17
17) Martedì 13 novembre (lezioni 33-34):
Teorema di Cipolla (Teorema 1.2.6 sugli
appunti di Zaccagnini): fissato a, esistono infiniti numeri composti
m tali che a^(m-1) congruo a 1 (mod m). I numeri di Carmichael.
Caratterizzazione di Korselt (senza dimostrazione): un numero n è di
Carmichael se e solo se n è privo di quadrati e se per ogni
fattore primo p che divide n si h (p-1)|(n-1). Lista dei primi 6 numeri di
Carmichael. Il numero di Hardy-Ramanujan
1729 e
i 'taxicab numbers'.
[Ste]
Capitolo 18.1, 18.2, 18.3.
18) Mercoledì 14 novembre (lezioni 35-36):
Esercitazione:
Scheda 3.
Scheda 4.
Scheda 5.
19 e 20)
Giovedì 15 novembre (lezioni 37-38-39-40):
Prima prova in itinere, aula V, ore 11-15.
/) Venerdì 16 novembre (lezioni //): Lezione cancellata per motivi di salute
21) Martedì 20 novembre (lezioni 41-42):
Il teorema di Fermat fornisce una condizione necessaria ma non sufficiente
per la primalità.
Ricerca dell'inverso di N (mod m) tramite Fermat
(complessità O(log^3 N)) o tramite l'identità di Bézout
(complessità O(log^2 N)). Generazione di primi random con l'algoritmo
di Fermat (algoritmo probabilista).
Numero di congruenze polinomiali R(x) congruo a 0 (mod p) con grado al
più p: ce ne sono 1 + (p^p-1)/(p-1).
Il teorema di Wilson si inverte
(fornisce un test di primalità però inefficiente).
[Zac]
Capitolo 1.2
22) Giovedì 22 novembre (lezioni 43-44):
Conseguenze del teorema di WIlson: Teorema: ognuna delle congruenze
x^(p-1)/2 congruo a 1 e x^(p-1)/2 congruo a 1 (mod p) ha esattamente
(p-1)/2 soluzioni, e l'unione delle soluzioni forma un sistema ridotto di
residui. Esponenti, radici primitive, indici, nella risoluzione delle
congruenze pure x^n congruo ad a (mod m). Definizione di ordine di un
elemento a (mod m) (exponent of a ). Elemento (o radice) primitivo (mod m).
Proprietà degli ordini (esponenti). Radici primitive e sistemi ridotti
di residui. Teorema di Gauss: esistono radici primitive solo per i moduli
M=1,2,4,p^k, 2p^k, con k positivo, p primo dispari.
Proposizione: per a> 3, si ha:
x^phi(2^a)/2 congruo ad 1 mod (2^a), quindi non esistono
radici primitive mod (2^a).
[Apo]
Capitolo 10.1, 10.2, 10.3.
23) Venerdì 23 novembre (lezioni 45-46):
Esistenza di radici primitive (mod p). Esistenza di radici primitive (mod p^a)
per ogni a>0. Esistenza di radici primitive (mod 2p^a) per ogni a.
Non esistenza di radici primitive per m diverso da 1, 2, 4, p^a, 2p^a.
Numero di radici primitive (mod m).
Esistenza di radici primitive (mod 2p^a) per ogni a. Non esistenza di
radici primitive per m diverso da 1, 2, 4, p^a, 2p^a.
Numero di radici primitive (mod m). Esercizi dalla
Scheda 6.
[Apo]
Capitolo 10.4, 10.5, 10.6, 10.7, 10.8 e 10.9
24) Martedì 27 novembre (lezioni 47-48):
Teoria degli indici. Applicazioni ed esempi alle congruenze lineari,
congruenze pure (o binomiali) e a quelle esponenziali.
[Apo]
Capitolo 10.10, 9.1, 9.2 e 9.3
oppure
[Ste]
Capitolo 20.1, 21.1, 21.2 e 21.3
25) Giovedì 29 novembre (lezioni 49-50):
Residui quadratici e
simbolo di
Legendre.
Simbolo di Legendre. Proprietà: periodicità, criterio di Eulero,
moltiplicatività. Calcolo di (-1|p) e di (2|p). Lemma di Gauss.
Criterio per la parità di m, con n^{(p-1)2} congruo a (-1)^m. (teorema
9.7).
[Apo]
Capitolo 9.1, 9.2, 9.3 e 9.4
26) Venerdì 30 novembre (lezioni 51-52):
La legge di reciprocità quadratica. Applicazioni.
[Apo]
Capitolo 9.5 e 9.6
27) Martedì 4 dicembre (lezioni 53-54):
Esercizi
della
Scheda 7.
28) Giovedì 6 dicembre (lezioni 55-56):
Generalità sui campi. Caratteristica infinita o finita. Teorema:
Cardinalità di un campo finito (potenza della caratteristica). Generalizzazione ai campi finiti di Eulero Fermat. Se il campo K
ha cardinalità q,
allora il polinomio X^q-X è completamente riducibile su K. I campi
finiti non sono algebricamente chiusi (il polinomio X^q-X+1 non ha
radici in K).
Estensioni. Elementi algebrici e trascendenti.
[PCat]
Capitolo 6.1
29) Venerdì 7 dicembre (lezioni 57-58):
Caratterizzazione degli elementi algebrici e trascendenti di un campo
F secondo la struttura delle loro
estensioni semplici su F.
Costruzione esplicita di un campo finito a 16 elementi: GF(16).
Le quattro operazioni.
[PCat]
Capitolo 6.1
[MwSlo]
Capitolo 3.2
30) Martedì 11 dicembre (lezioni 59-60):
Costruzione generale di GF(p^m) dato un polinomio: - irriducibile, - a
coefficienti in GF(p), - di grado m. Proprietà di un campo finito: vale
il teorema di Fermat (ogni elemento soddisfa x^(p^m)=x); Il gruppo
moltiplicativo di un campo finito è ciclico; esiste un elemento
primitivo (che genera tutto il campo); vale (x+y)^p=x^p+y^p;
vale (x+y)^(p^s)=(x)^(p^s)+(y)^(p^s); il polinomio X^(p^m) -X si
fattorizza su GF(p^m) come prodotto di fattori lineari (X-b), al variare di b
elemento di GF(p^m).
Il polinomio minimo di un elemento di GF(p^m) e sue proprietà. Esempi.
Polinomi primitivi. Teorema di esistenza di un campo finito
(via estensioni...). Teorema di unicità (a meno di isomorfismo) di
un campo di cardinalità fissata.
[MwSlo]
Capitolo 4.1, 4.2
31) Giovedì 13 dicembre (lezioni 61-62):
Struttura dei sottocampi di un campo:
il reticolo dei sottocampi di GF(p^m) è isomorfo al reticolo dei
divisori di m. b e b^p hanno lo stesso polinomio minimo.
[MwSlo]
Capitolo 4.3
32) Venedì 14 dicembre (lezioni 63-64):
33) Martedì 18 dicembre (lezioni 65-66):
34) Giovedì 20 dicembre (lezioni 67-68):
35) Venerdì 21 dicembre (lezioni 69-70):
Introduzione alla crittografia. Un po' di termonologia. Un po' di storia.
I cifrari per sostituzione. Il cifrario cesareo. La sostituzione
monoalfabetica. Il cifrario per sostituzione polialfabetico (cifrario
di Vigenère. Cifrari per trasposizione. Tecniche di crittografia.
Sistemi simmetrici (a chiave segreta) e asimmetrici (a chiave pubblica).
Vantaggi e svantaggi. Sistemi misti. Scambio della chiave di Diffie-Hellmann.
Sistema crittografico RSA.
Le classi ciclotomiche
(mod p^m-1). Esempi.
Classi ciclotomiche: il polinomio minimo di alfa^i è il prodotto di
fattori
(x-a^j) al variare di j nella stessa classe ciclotomica di i. Funzioni
simmetriche elementari
I coefficienti del polinomio che si ottiene moltiplicando i fattori
lineari (x-alfa^i) al variare di i in una classe ciclotomica è
a coefficienti in GF(p).
Teorema: X^q-X è prodotti di tutti i
polinomi irriducibili su GF(p) di grado d, con d che divide m. Esempi.
Esempi di fattorizzazioni: conteggio di polinomi irriducibili su GF(2) di
grado 1, 2, 3, 4. Reciproco di un polinomio. Uso delle classi ciclotomiche
per il calcolo dei fattori irriducibili in X^q-X, usando le funzioni
simmetriche delle radici. Automorfismi di GF(p^m). Il gruppo di Galois
di un campo finito. Teorema: Tale gruppo è ciclico di
ordine m grado dell'estensione.
[PCatt]
Capitolo 3.6
Automorfismi di GF(p^m). Il gruppo di Galois
di un campo finito. Teorema: Tale gruppo è ciclico di
ordine m grado dell'estensione.
Numero dei polinomi irriducibili di grado m su GF(q) tramite
l'inversione di Möbius. Corollario: per ogni q(=p^h) e per
ogni m esiste un polinomio irriducibile su GF(q) di grado m.
Radici p-sime in GF(q), con q=p^m. Radici quadrate. Residui quadratici in un
campo finito. L'elemento -1 è residuo quadratico se e solo se q
è congruo a 1 modulo 4. Teorema: per p diverso da due,
metà degli elementi
sono residui quadratici. Radici n-sime dell'unità in un campo
finito: caratterizzazione delle radici n-sime primitive (quando n divide
q-1); numero di radici n-sime di 1 è il massimo comune
divisore tra n e q-1. Estensioni quadratriche con q congruo a 3 modulo 4.
[MwSlo]
Capitolo 4.6 e 4.7.
[Kob]
Capitolo II par 2 (pag 42 e 43)
[MwSlo]
Capitolo 4.4 e 4.5
[]
Capitolo
[]
Capitolo
36) Gennaio 8 (71-72-73-74):
Seconda prova in itinere