Teoria dei numeri e Crittografia: lezione del 3 ottobre 2011

Teoria dei numeri e Crittografia: lezione del 3 ottobre 2011

Alcuni dei principali 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 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”

Lo scopo di questa teoria (fondata da Bachman e Landau) è quello di confrontare la “velocità di crescita” di una funzione con quella di una funzione di riferimento: la teoria 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.

Una definizione classica è la seguente: date due funzioni f, g, diremo che f è dominata da g (o che g domina f) se esistono 2 costanti reali c, k tali che per ogni x c si abbia f(x) kg(x).

Esempio. La funzione f(x)=3x

+9 è dominata dalla funzione g(x)=x

: infatti per x3 si ha x

9 da cui

f(x)=3x

+93x

+x

=4x

=4g(x)

e si ottiene la condizione della definizione, con le costanti c=3, k=4 .

La condizione che la funzione f sia dominata dalla funzione g è equivalente alla seguente: esistono 2 costanti reali c, k tali che per ogni xS, xc 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 in assoluto: se infatti x

è un qualunque numero naturale  c, posto

k

=max{f(1)/g(1)),f(2)/g(2),..., f(x

-1)/g(x

-1),k}

si ha f(x)/g(x) k

per ogni numero naturale x (infatti se x<x

allora ovviamente f(x)/g(x) k

e se xx

c egualmente f(x)/g(x) k  k

).

Dunque la definizione della condizione f è dominata da g si può dare in modo equivalente nel modo seguente (almeno per la categoria di funzioni di cui ci occupiamo): 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 xc (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)=a

(per ogni base reale a>1) è dominata dalla funzione g(x)=x! .

Fissiamo un qualunque numero naturale ca e notiamo che per ogni xca si ha : f(x)/g(x)=a

/x!=(a

/c!){a

/[(c+1)(c+2)…x]}(a

/c!)

(l’ultimo  è giustificato dall’osservazione che nella frazione a

/[(c+1)(c+2)…x] il numeratore ed il numeratore sono entrambi prodotto di x-c fattori, e si possono accoppiare i fattori del numeratore e denominatore in modo che ogni fattore del numeratore sia < del corrispondente fattore del denominatore).

Dunque f(x)/g(x)k (dove k=(a

/c!)) per ogni xc 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 in un certo senso la funzione f(x) cresce non più velocemente di g(x) (perchè il rapporto f(x)/g(x) è limitato).

In questo senso la teoria permette di confrontare le velocità di crescita di 2 funzioni.

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 xc (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:

O(g) = { funzioni f / f è dominata da g }.

Quindi g domina f  fO(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 fO(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 O(g).

Nota: in molti testi il fatto che la funzione f sia dominata dalla funzione g 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 simbologia è 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” (come dimostrano le proprietà riflessiva e transitiva).

Se f domina g e se g domina f, diremo che l’ordine di f è uguale all’ordine di g: questa terminologia è ovviamente giustificata dal fatto che, per quanto dimostrato sopra, la proprietà che le funzioni f, g si dominano a vicenda equivale all’eguaglianza insiemistica O(f)=O(g).

Dal punto di vista pratico si ha O(f)=O(g) se f, g hanno in un certo senso 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 l’ordine di f é strettamente minore dell’ordine di

g: ciò in pratica significa che in un certo senso la “velocità di crescita” di f è strettamente minore di

quella di g.

Per avere una stima della velocità di crescita della funzione f , spesso cercheremo una funzione di riferimento “ben conosciuta” g tale che f sia dominata da g (quindi tale che fO(g) o equivalentemente O(f)O(g)) : non sempre troveremo una g “ottimale” (sarebbe tale se fosse O(f)=O(g) quindi con f , g dello stesso ordine) ma per gli scopi pratici potrà spesso bastare.

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 :

1) Se tale limite esiste finito è noto (da risultati di Analisi) che il rapporto f(x)/g(x) è limitato, dunque g domina f , O(f)O(g), ed f è di ordine O(g).

2) Se tale limite esiste ed è = , allora g non domina f , perché è noto (sempre da risultati di Analisi) che in questo caso il rapporto f(x)/g(x) è illimitato.

3) Da 1) e 2) segue anche che se tale limite esiste finito ed è non nullo allora O(f)=O(g)(quindi f , g hanno lo stesso ordine): infatti detto l il limite, si ha che il limite del rapporto g(x)/f(x) per x è l

<, e basta applicare la proprietà 1) per ottenere che f, g si dominano reciprocamente. Se invece tale limite esiste finito ed è = 0 allora O(f)<O(g) (quindi f ha ordine strettamente inferiore a g): infatti per la 1) g domina f , ma per la 2) f non domina g essendo  il limite del rapporto g(x)/f(x) per x.

4) Se tale limite non esiste, niente si può dire, se non con ulteriori considerazioni, sugli ordini di f, g (che potrebbero anche non essere confrontabili).

Esempi.

1) Date le funzioni f , g definite rispettivamente da:

f(x)=1 per x dispari, f(x)=x per x pari g(x)=x per x dispari, g(x)=1 per x pari

non esiste il limite del rapporto f(x)/g(x) per x, in quanto f(x)/g(x)=1/x per x dispari, f(x)/g(x)=x per x pari. Poiché il rapporto f(x)/g(x) è illimitato si deduce che g non domina f, ma poiché anche il rapporto g(x)/f(x) è illimitato (perché g(x)/f(x)=x per x dispari e g(x)/f(x)=1/x per x pari) si deduce che neanche f domina g : dunque gli ordini di f e g non sono “confrontabili”.

2) Date le funzioni f , g definite rispettivamente da:

f(x)=1/x per x dispari, f(x)=x per x pari g(x)=2/x per x dispari, g(x)=x

per x pari

non esiste il limite del rapporto f(x)/g(x) per x, in quanto f(x)/g(x)=1/2 per x dispari, f(x)/g(x)=1/x per x pari. Poiché però il rapporto f(x)/g(x) è limitato si deduce che g domina f, ma poiché invece il rapporto g(x)/f(x) è illimitato (perché g(x)/f(x)=2 per x dispari e g(x)/f(x)=x per x pari) si deduce che f non domina g : dunque O(f)<O(g) ed f ha ordine strettamente inferiore a g.

Per valutare l’ordine di una funzione f si considerano varie categorie di funzioni g (di riferimento) con cui confrontare l’ordine di f, ottenendo vari “tipi” di ordine.

La funzione f ha ordine polinomiale di grado n (dove n è un intero non negativo) se f ha ordine O(g) dove g è una funzione polinomiale di grado n della forma:

g(x) = a

+a

x+……+a

x

con i coefficienti a

reali, e con a

≠0.

Si noti che in tale caso si ha O(a

+a

x+……+a

x

)= O(x

) perché il limite del rapporto f(x)/g(x) per x è a

≠0.

Dunque equivalentemente: la funzione f ha ordine polinomiale di grado n (dove n è un intero non

negativo) se f è di ordine O(x

).