Teoria dei numeri e Crittografia: lezione del 5 ottobre 2011
Abbiamo definito la funzione f (definita sui numeri naturali, a valori reali >0) di 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) = a0+a1x+……+anxn con i coefficienti ai reali, e con an≠0.
o equivalentemente se f è di ordine O(xn).
Nel caso particolare n=0 si ha: f ha ordine O(1) se e solo se la funzione f(x) è limitata.
Invece per n=1, 2 si ottengono le funzioni di ordine lineare e quadratico rispettivamente.
Nota: La situazione ideale per stimare la velocità di crescita della funzione f sarebbe quella in cui troviamo una funzione di riferimento g di ordine “minimo” fra quelle che dominano f , ossia tale che O(f)=O(g) (in modo che f, g abbiano lo stesso ordine): non sempre questo è possibile, ma per i nostri scopi sarà spesso sufficiente trovare una g di ordine abbastanza “basso” che domina f .
Per esempio se una funzione f ha ordine lineare (quindi se fO(x)), allora a maggior ragione f ha ordine quadratico (ossia fO(x2)), perché O(x)O(x2) (in quanto il limite del rapporto x/x2 è 0 per x). Ovviamente l’affermazione “f ha ordine lineare” fornisce una stima migliore sulla velocità di crescita di f rispetto all’affermazione “f ha ordine quadratico”.
Altre funzioni di riferimento interessanti, oltre quelle polinomiali, sono le funzioni del tipo g(x)=xt dove t è un esponente reale 0 (non necessariamente intero): un esempio é g(x)=x1/2=x.
Per questa categoria di funzioni (che comprendono come caso particolare quelle polinomiali) notiamo che al crescere dell’esponente t cresce strettamente l’ordine della funzione xt: se 0 ≤ t < s allora l’ordine di xtè strettamente minore di quello di xs perché è 0 il limite del rapporto xt/xs=xt-s per x (essendo t-s<0).
Come conseguenza notiamo che se una funzione f ha ordine O(xt) (con t esponente reale 0 non necessariamente intero), allora f ha certamente ordine polinomiale : infatti se poniamo n=t (la cosiddetta “parte intera” di t ossia il massimo numero intero ≤ n), si ha ovviamente t<n+1 da cui:
O(xt) O(xn+1)
quindi f ha ordine polinomiale O(xn+1) .
Diremo che la funzione f ha ordine logaritmico se f ha ordine O(g) dove g è una funzione logaritmica della forma g(x) = loga(x) per una opportuna base reale a>1.
Nota: in effetti la funzione g(x) = loga(x) assume valori reali positivi tranne che per x=1 (dove si annulla), quindi a rigor di termini tale funzione non farebbe parte delle funzioni esaminate nella nostra teoria (definite sui numeri naturali e a valori reali positivi). In pratica non terremo conto di questa eccezione (a cui si potrebbe in ogni caso facilmente ovviare sostituendo g(x)=loga(x) per esempio con g(x)= loga(x)+1 ) .
Notiamo che tutte le funzioni logaritmiche hanno lo stesso ordine, indipendentemente dalla base >1 scelta: infatti se a,b>1 sono due basi, dalla formula loga(x) = loga(b)logb(x) segue che il rapporto loga(x) / logb(x)= loga(b) è costante dunque O(loga(x))= O(logb(x)) .
Notiamo anche che O(1)O(loga(x))O(x) perché per x si ha:
lim [1/ loga(x)] = lim [loga(x)/x] = 0.
La funzione f ha ordine esponenziale se f ha ordine O(g) dove g è una funzione esponenziale della forma g(x) = ax per una opportuna base reale a>1.
Notiamo che al crescere della base a cresce strettamente l’ordine della funzione esponenziale ax : se 1<a<b l’ordine di axè strettamente minore di quello di bx perché 0= lim ax/bx =lim (a/b)x per x
(essendo a/b<1).
Se a>1 ponendo k=logea>0 si ha ax=ekx dunque si può dire in modo equivalente che la funzione f ha ordine esponenziale se f ha ordine O(ekx) per una opportuna costante reale k>0 .
Una qualunque funzione di ordine polinomiale O(xn) (con n intero non negativo) è sempre di ordine strettamente minore di qualunque funzione di ordine esponenziale O(ekx) (con k>0): infatti applicando n volte la regola di de l'Hôpital si ottiene che il limite (per x) del rapporto xn/ekx coincide con il limite del rapporto (n!)/(knekx) che è 0.
Una funzione ha ordine superpolinomiale se ha ordine strettamente maggiore di qualunque funzione polinomiale (per esempio se ha ordine esponenziale) ed ha ordine subesponenziale se ha ordine strettamente minore di qualunque funzione esponenziale (per esempio se ha ordine polinomiale).
Esistono funzioni che sono di ordine sia superpolinomiale che subesponenziale (quindi di ordine strettamente compreso fra il polinomiale e l’esponenziale): per esempio la funzione e(x/logx).
Si può infatti dimostrare, con gli usuali metodi analitici, che il limite dei rapporti:
xn/e(x/logx) e(x/logx)/ax
è 0, per x (n intero non negativo, a reale >1).
Esistono anche funzioni di ordine strettamente maggiore dell’ordine esponenziale (superesponenziali) : in un esempio precedente si è dimostrato che la funzione esponenziale f(x)=ax (per ogni base reale a>1) è dominata dalla funzione “fattoriale” g(x)=x! . D’altronde, con metodi analoghi a quelli dell’esempio citato, si può verificare che il rapporto x!/ax è illimitato, dunque g non è dominata da f, e si conclude che O(ax) O(x!), deducendo che la funzione fattoriale è superesponenziale.
Schema delle funzioni più comuni per ordine strettamente crescente:
O(1) O(loga(x)) O(x) O(x2) O(x3) …. O(e(x/logx))…. O(ax) ….. O(x!)
(dove a è un reale >1, tutte le funzioni logaritmiche dello stesso ordine, le funzioni esponenziali sono di ordine crescente al crescere delle base a ).
Compatibilità della relazione di dominazione con le operazioni fra funzioni.
Notiamo prima di tutto che se f è una funzione e se k>0 è una costante reale, posto g=kf (cioè definendo g(x)=kf(x) per ogni x) si ha ovviamente O(f)=O(g), essendo costante (quindi limitato) il rapporto f/g=k .
La relazione di dominazione è “compatibile” con la somma e il prodotto di funzioni: se f1 ha ordine O(g1), e se f2 ha ordine O(g2) allora f1f2 ha ordine O(g1g2) ed f1+f2 ha ordine O(g1+g2), dove il prodotto delle funzioni f,g è definito da (fg)(x)=f(x)g(x) e la somma da (f+g)(x)=f(x)+g(x)).
Infatti se esistono costanti k, m tali che f1(x) kg1(x), f2(x) mg2(x) allora (f1f2)(x)=f1(x)f2(x) kmg1(x)g2(x)=km(g1g2)(x)
(f1 +f2)(x)=f1(x)+f2(x) h(g1(x)+g2(x))=h(g1 +g2)(x) dove h=max{k, m}.
Da questi risultati ovviamente segue che se O(f1)=O(g1), O(f2)=O(g2) allora:
O(f1f2)=O(g1g2) ed O(f1 +f2)=O(g1 +g2).
In particolare se f1, f2 hanno entrambe ordine O(f), allora f1+f2 ha ordine O(2f) e poiché O(2f)=O(f) (vedere l’osservazione all’inizio del paragrafo), si conclude che f1+f2 ha ordine O(f).
Notiamo inoltre che per ogni coppia di funzioni f, g si ha:
f è di ordine O(f+g) (*)
(perché, essendo le funzioni a valori positivi, si ha f(x)<f(x)+g(x), dunque f+g domina f).
Inoltre:
f ha ordine O(g) O(f+g)=O(g)
Infatti: se f ha ordine O(g), allora (come osservato sopra) g è di ordine O(f+g), ma anche (per la compatibilità della somma e la proprietà riflessiva) f+g è di ordine O(g+g)=O(2g)=O(g), dunque in totale O(f+g)=O(g) ; viceversa se O(f+g)=O(g) allora per la (*) f è di ordine O(f+g) .
Quest’ultimo risultato dimostra che nella stima dell’ordine della somma di funzioni “prevale” quella di ordine maggiore (se gli ordini delle 2 funzioni sono confrontabili): se per esempio f ha ordine polinomiale e g ordine esponenziale, la somma f+g avrà ordine esponenziale.
La compatibilità della relazione di dominazione con il prodotto di funzioni implica invece per esempio che il prodotto di funzioni di ordine polinomiale (risp. esponenziale) è di ordine polinomiale (risp. esponenziale): infatti se f ha ordine O(xn), e se g ha ordine O(xn) (con n, m interi
0) allora fg ha ordine O(xnxm)=O(xn+m); se invece f ha ordine O(ekx), e se g ha ordine O(ehx) (con k,h reali>0) allora fg ha ordine O(ekxehx)=O(e(k+h)x).
D’altronde se f ha ordine polinomiale O(xn) (con n intero 0), e se g ha ordine esponenziale O(ekx) (con k reale >0), allora fg ha ordine O(xnekx) O(ekx) (in quanto per x si ha che lim[xn/ (xnekx)]=lim(1/ekx)=0 ) quindi fg ha ordine esponenziale.
Algoritmi
Gli algoritmi che studieremo nel corso saranno per lo più algoritmi aritmetici relativi ai numeri naturali: nella nostra trattazione un algoritmo sarà quindi un procedimento composto da un valore in entrata (input) costituito da uno (o più) numeri naturali, da un numero finito di passaggi (steps), e da un valore in uscita (output) costituito da uno (o più) numeri (non necessariamente naturali) oppure da una affermazione relativa all’input.
Esempi di algoritmi aritmetici:
a) algoritmo della divisione: input a,b (numeri naturali); steps: si calcolano 2 interi non negativi q,r tali che a=bq+r, con r<b (esistono diversi metodi per calcolarli); si esce con output q (quoziente), r (resto) (in questo caso l’output è una coppia di interi non negativi).
b) test di primalità “ingenuo”: input n (numero naturale >1); steps: per i=2,3,…,n-1 si verifica se i è divisore di n (per esempio dividendo n per i con l’algoritmo della divisione e verificando se il resto è nullo); se per qualche i il resto è nullo, si esce con output “n non è primo”, se per tutti gli i il resto è non nullo si esce con output “n è primo” (in questo caso l’output è un’affermazione relativa all’input).
Complessità di un algoritmo
La complessità di un algoritmo è una misura delle risorse necessarie per eseguirlo: al giorno d’oggi ogni algoritmo viene eseguito da un computer.
Ci interesseremo solo di complessità “temporale” (quindi relativa al tempo di esecuzione dell’algoritmo) e non per esempio di quella “spaziale” (relativa allo spazio occupato nella memoria del computer dai dati, anche temporanei, utilizzati durante l’esecuzione dell’algoritmo).
I dati numerici coinvolti in un algoritmo saranno rappresentati in base 2 cioè in forma binaria.
Ricordiamo un ben noto risultato aritmetico (che dimostreremo formalmente in seguito): fissato un numero naturale b>1 (base), ogni numero naturale a si può rappresentare (in modo unico) nella forma
a=ak-1bk-1+ak-2bk-2+…+a1b1+a0b0 (detta rappresentazione di a in base b) dove gli ai (cifre) sono k numeri interi tali che 0 ai b-1, e dove ak-1≠0.
In tale caso si usa la simbologia a=(ak-1, ak-2,….,a1, a0)b .
In particolare (scegliendo la base b=2) ogni numero naturale a ha una rappresentazione binaria della forma
a=ak-1k-1+ak-22k-2+…+a121+a020
dove gli ai (cifre binarie o bits) assumono come valori possibili 0,1, e dove ak-1=1: useremo in tale caso la simbologia a=(ak-1, ak-2,….,a1, a0), sottintendendo la base b=2.
Data la rappresentazione del numero naturale a in base b>1 a=ak-1bk-1+ak-2bk-2+…+a1b1+a0b0
il numero naturale k (coincidente con il numero di cifre usate nella rappresentazione) è detto lunghezza di a in base b ed è indicato con il simbolo Lb(a).
Nel caso di rappresentazione binaria useremo semplicemente il simbolo L(a) invece di L2(a), e parleremo di lunghezza di a, sottintendendo la base 2.
La lunghezza k=Lb(a) di a in base b si può caratterizzare con la seguente proprietà:
k è il più grande dei numeri naturali che soddisfano la proprietà bk-1 a o equivalentemente bk-1 a < bk.
Infatti basta osservare che a=ak-1bk-1+ak-2bk-2+…+a1b1+a0b0 ak-1bk-1 bk-1 (perchè a0,a1,….,ak-20 ed ak-1 1) e che (essendo le cifre ai (b-1)) si ha anche:
a (b-1)(bk-1+bk-2+…+b1+b)=(bk-1)<bk . Da ciò segue anche che se k=Lb(a) si ha:
k-1 logb(a) < k
dunque k-1 è il più grande intero logb(a), ossia k-1 è la parte intera di logb(a):
k-1 = logb(a) , Lb(a) = k = logb(a) +1
In particolare nel caso b=2 la lunghezza di a è L(a) = log2(a) +1 .
E’ utile citare alcune proprietà della lunghezza (binaria) della somma e del prodotto di due generici numeri naturali a, b:
1) se k=max(L(a),L(b)) allora L(a+b) = k oppure L(a+b) = k+1 2) L(ab) = L(a)+L(b)-1 oppure L(ab) = L(a)+L(b)
Infatti, ponendo k=L(a), h=L(b) e supponendo per esempio h k = max(L(a),L(b)) da:
2k-1 a < 2k 2h-1 b < 2h segue:
2k-1< 2k-1+2h-1 a+b< 2k+2h 2k+2k = 2k+1 2k-12h-1= 2k+h-2 ab< 2k2h = 2k+h
e ricordando che L(a+b)=s è il più grande dei numeri naturali che soddisfano 2s-1 a+b, mentre L(ab)=t è il più grande dei numeri naturali che soddisfano 2t-1 ab, si conclude che k s< k+2, e che k+h-1 t < k+h+1, ossia la 1) e la 2).
Se vogliamo dare una “stima” del tempo necessario affinché un algoritmo venga eseguito, e quindi della sua “complessità” di calcolo, dobbiamo scegliere delle operazioni “elementari”, che fungano da “unità di misura” e mediante le quali si possano costruire tutte le altre operazioni eseguite nei
diversi algoritmi; sceglieremo come operazione elementare l’operazione di somma sui singoli bits con riporto (carry).
