Teoria dei numeri e Crittografia: lezione del 21 marzo 2011
Alcuni argomenti trattati nel corso saranno i seguenti: studio della Teoria dei Numeri (soprattutto l’aritmetica dei numeri interi e in particolare dei numeri naturali, cioè degli interi >0), costruzione di alcuni algoritmi che coinvolgono i numeri interi, applicazioni della teoria dei numeri alla Crittografia.
Testo consigliato:
Baldoni, Ciliberto, Piacentini Cattaneo: “Aritmetica, Crittografia e Codici”
Altri testi utili:
Rosen: “Elementary Number theory”
Koblitz: “A Course in Number Theory and Cryptography”
(tutti disponibili per la consultazione presso la Biblioteca del Dipartimento).
Teoria della “Big-O” (Bachman-Landau)
Questa teoria ha come obiettivo quello di confrontare la “velocità di crescita” di una funzione con quella di una funzione di riferimento, e sarà poi applicata allo studio della complessità degli algoritmi.
Tutte le funzioni che considereremo sono definite sull’insieme N dei numeri naturali e assumono valori reali positivi, e questo porterà ad alcune semplificazioni rispetto alla teoria classica.
Date due funzioni f, g, diremo che f è dominata da g ( equivalentemente g domina f) se esistono 2 costanti reali c, k tali che per ogni xc si abbia f(x)kg(x).
Esempio. La funzione f(x)=3x2+9 è dominata dalla funzione g(x)=x2: infatti per x3 si ha x29 da cui
f(x)=3x2+93x2+x2=4x2=4g(x)
e si ottiene la condizione della definizione, con le costanti c=3, k=4 .
Ovviamente la condizione che la funzione f sia dominata dalla funzione g è equivalente alla seguente: esistono 2 costanti reali c, k tali che per ogni xS, xc si abbia f(x)/g(x)k , (dunque il rapporto f(x)/g(x) è limitato, per x “abbastanza grande”).
Ma possiamo osservare che la nostra ipotesi che le funzioni siano definite sull’insieme N dei numeri naturali implica che in tale caso il rapporto f(x)/g(x) è limitato: se infatti x0 è il più grande numero intero c+1 (la cosiddetta “parte intera” di c+1 indicata spesso con il simbolo c+1 : notare che certamente x0c ), posto
k0=max{f(1)/g(1)),f(2)/g(2),..., f(x0-1)/g(x0-1),k}
si ha f(x)/g(x)k0 per ogni numero naturale x (infatti se x<x0 allora ovviamente f(x)/g(x)k0 e se xx0c egualmente f(x)/g(x)kk0).
Dunque la definizione della condizione f è dominata da g si può dare in modo equivalente nel modo seguente (almeno per funzioni definite sui numeri naturali): esiste una costante reale k tale che per ogni x si abbia f(x)kg(x).
Tuttavia dal punto di vista operativo, per verificare che f è dominata da g talvolta é più facile trovare un valore della costante k che limita il rapporto f(x)/g(x) per xc (con c costante opportuna) piuttosto che trovare un valore k che limita il rapporto f(x)/g(x) per ogni valore di x.
Esempio. Verifichiamo che la funzione esponenziale f(x)=ax (per ogni base reale a>1) è dominata dalla funzione g(x)=x! .
Fissiamo un qualunque numero naturale ca e notiamo che per ogni xca si ha : f(x)/g(x)=ax/x!=(ac/c!){ax-c/[(c+1)(c+2)…x]}(ac/c!)
(l’ultimo è giustificato dall’osservazione che nella frazione ax-c/[(c+1)(c+2)…x] il numeratore ed il numeratore sono entrambi prodotto di x-c fattori, ed ogni fattore del numeratore è < del corrispondente fattore del denominatore).
Dunque f(x)/g(x)k (dove k=(ac/c!)) per ogni xc e si conclude che f è dominata da g : sarebbe stato più difficile calcolare una costante k tale che f(x)/g(x)k per ogni valore di x.
Dal punto di vista pratico affermare che la funzione f è dominata dalla funzione g equivale ad affermare che, al crescere di x, la funzione f(x) cresce non più velocemente di g(x): infatti se f(x)/g(x)k e se consideriamo x1,x2S, x2>x1 si avrà:
f(x2)/f(x1) kg(x2)/kg(x1) g(x2)/g(x1).
Se dunque si conosce una valutazione della “velocità” di crescita della funzione g, si può valutare un maggiorante di quella della funzione f: se per esempio g(x)=x2, e se g domina f, si può dedurre che al raddoppiare di x il valore di f(x) al più quadruplica.
Nota: in molti testi il fatto che la funzione f sia dominata dalla funzione g si esprime con la frase “f è di ordine g” e si rappresenta con il simbolo f = O(g) (simbolo della big-O introdotto da Bachman nel 1894 e in seguito diffuso dai lavori di Landau). Tale terminologia è però poco precisa dal punto di vista formale, perché la relazione di dominazione è più una relazione di “minore o uguale” che una relazione di “eguaglianza”: useremo quindi altre terminologie che rendono più corretta la trattazione.
Ovviamente la relazione di dominazione è riflessiva perché ogni funzione f domina sé stessa (basta scegliere nella definizione il valore 1 per la costante k): più in generale se f(x) g(x) per ogni xc (con c costante) allora g domina f .
Inoltre la relazione di dominazione è transitiva: se h domina g e se g domina f, allora h domina f:
infatti se esistono costanti reali k, m tali che si abbia g(x)kh(x), f(x)mg(x), allora si avrà f(x)(mk)h(x), con mk costante reale.
Per ogni funzione g indicheremo con O(g) l’insieme delle funzioni dominate da g.
Quindi g domina f fO(g).
Dalla transitività della relazione di dominazione segue facilmente che:
g domina f O(f)O(g).
Infatti: se g domina f , per transitività g domina ogni funzione h che sia dominata da f, da cui O(f)O(g); viceversa se O(f)O(g) per la proprietà riflessiva si ha fO(f)O(g) quindi g domina f.
Chiameremo ordine della funzione f l’insieme O(f) : se f è dominata dalla funzione g (quindi equivalentemente se O(f)O(g)) diremo che f ha ordine ≤ all’ordine di g e scriveremo O(f)O(g).
Se f domina g e se g domina f, diremo che l’ordine di f è uguale all’ordine di g: per quanto dimostrato sopra, ciò equivale all’eguaglianza insiemistica O(f)=O(g).
Dal punto di vista pratico O(f)=O(g) se f, g hanno la stessa “velocità di crescita”.
Se O(f)O(g) ma O(f)O(g) (quindi se g domina f ma non viceversa, o equivalentemente se O(f)O(g) con inclusione propria) diremo che f ha ordine strettamente < all’ordine di g e scriveremo O(f)<O(g): ciò in pratica significa che la “velocità di crescita” di f è strettamente minore di quella di g.
Vedremo che un criterio per confrontare gli ordini delle funzioni f, g è quello di studiare il limite del rapporto f(x)/g(x) per x.
