Teoria dei numeri e Crittografia: lezione del 12 ottobre 2011

Teoria dei numeri e Crittografia: lezione del 12 ottobre 2011

Nella lezione precedente abbiamo detto che sceglieremo come operazione elementare (che funga da “unità di misura” della complessità di un algoritmo) l’operazione di somma sui singoli bits con riporto (carry).

Tale operazione, dati 2 bits da sommare x,y=0,1 e fissato un valore c=0,1 del carry, calcola il bit risultato x+y e il nuovo valore c

del carry, secondo le regole esposte nella seguente tabella:

Nella prima e seconda colonna vi sono rispettivamente il valore del bit x e il valore del bit y; nella terza colonna il valore c del carry prima della somma;

nella quarta il valore del bit somma x+y; nella quinta il nuovo valore aggiornato c

del carry dopo la somma. Per esempio se x=1, y=0 e se il carry (prima della somma) è c=1, allora dalla quarta riga si ricava il bit somma x+y=0 (quarta colonna), e il valore aggiornato del carry c

=1 (quinta colonna).

Formalmente l’operazione di somma sui singoli bits con riporto é una funzione:

BitSum: {0,1}x{0,1}x{0,1}  {0,1}x{0,1} definita da BitSum(x,y,c)=(x+y,c

)

e in genere essa è implementata nell’hardware nel processore centrale (CPU) del computer.

Se trascuriamo il tempo che il computer impiega per altri tipi di operazioni più veloci (accesso alla memoria, operazioni di shift, confronto fra bits, scrittura di bits etc..) possiamo ragionevolmente supporre che il tempo totale dell’algoritmo sia proporzionale al numero di operazioni elementari eseguite (secondo una costante di proporzionalità che all’incirca coincide con il tempo impiegato dal computer per eseguire una operazione elementare).

(Nota: E’ ovvio che la nostra scelta dell’operazione BitSum come operazione elementare è dovuta al fatto che ci occuperemo di algoritmi di tipo “aritmetico”. Per altre categorie di algoritmi potrebbe essere invece opportuno una scelta diversa: per esempio per gli algoritmi di ordinamento (sorting) sarebbe opportuno scegliere come operazioni elementari quelle di confronto di bits e di accesso alla memoria per la lettura e scrittura dei dati da ordinare).

E’ opportuno che la nostra stima del tempo di esecuzione dell’algoritmo sia funzione della

“grandezza” dell’input, e dunque dobbiamo scegliere un modo per misurare quest’ultima: poiché le operazioni elementari agiscono sui singoli bits, è naturale ricorrere al già visto concetto di lunghezza di un numero naturale nella sua rappresentazione binaria, cioè al numero di bits 0,1 utilizzati per rappresentarlo.

Dato un algoritmo, definiremo taglia dell’input la lunghezza dell’input (se esso è costituito da un solo numero naturale) oppure la lunghezza massima dei numeri naturali che costituiscono l’input (se esso appunto è costituito da più numeri naturali).

Dato un algoritmo A potremmo allora definire una funzione Time

(x) come il numero di operazioni elementari eseguite dall’algoritmo A quando l’input ha taglia x: in questo modo moltiplicando tale valore per il tempo impiegato dal computer per svolgere una singola operazione elementare potremmo ottenere una stima abbastanza valida del tempo impiegato per eseguire l’algoritmo, sempre quando l’input ha taglia x.

Tale definizione non sarebbe però univoca perché due diversi input di eguale lunghezza x potrebbero dar luogo a un diverso numero di operazioni elementari nell’esecuzione dell’algoritmo.

x y c x+

y c

1

0 0 0 0 0

0 0 1 1 0

1 0 0 1 0

1 0 1 0 1

0 1 0 1 0

0 1 1 0 1

1 1 0 0 1

1 1 1 1 1

Definiremo allora invece in modo più preciso la funzione Time

(x) (o più brevemente T

(x)) come il numero di operazioni elementari eseguite dall’algoritmo A quando l’input ha taglia x, nel caso peggiore (cioè nel caso in cui il numero di operazioni elementari è il massimo, fra tutti i casi in cui l’input ha taglia x).

Possiamo dunque considerare T

(x) come una funzione nella variabile x (con x che assume valori naturali) a valori naturali (perché il numero di operazioni elementari è sempre un numero naturale):

nei casi concreti non saremo però interessati a conoscere il valore “esatto” di T

(x) (che spesso è difficile da calcolare) ma piuttosto a stimare la sua “velocità di crescita” cioè in che modo cresce il numero di operazioni elementari (e quindi il tempo di esecuzione dell’algoritmo) al crescere della taglia dell’input.

In questa stima ci aiuterà ovviamente la “teoria della big-O”: cercheremo opportune funzioni g(x) tali che T

(x) ha ordine O(g): diremo in tal caso che l’algoritmo A ha complessità computazionale O(g) (o semplicemente complessità O(g)).

In particolare diremo che l’algoritmo A ha complessità polinomiale se la funzione T

(x) è di ordine polinomiale, e che l’algoritmo A ha complessità esponenziale se la funzione T

(x) è di ordine esponenziale.

Consideremo efficienti gli algoritmi di complessità polinomiale, e non efficienti quelli di complessità superiore (cioè superpolinomiale), per esempio esponenziale.

Negli algoritmi efficienti , al crescere della taglia x dell’input, il tempo di esecuzione cresce molto meno velocemente che negli altri algoritmi: tuttavia è utile osservare che, per un fissato valore della taglia x dell’input, un algoritmo di complessità polinomiale può avere un tempo di esecuzione più alto di un algoritmo di complessità esponenziale, e quindi essere meno efficiente (per quel particolare valore x).

Esempio: Siano dati l’algoritmo A con T

(x)=x

(di complessità polinomiale) e l’algoritmo B con T

(x)=2

(di complessità esponenziale). Per un input di lunghezza x=32 (quindi un input con 32 cifre binarie) l’algoritmo A esegue (nel caso peggiore) 32

=2

operazioni elementari, mentre l’algoritmo B ne esegue 2

(quindi un numero inferiore): se ogni operazione elementare è eseguita in 1 milionesimo di secondo, l’algoritmo A impiega (nel caso peggiore) circa 9 ore e mezza, l’algoritmo B circa 1 ora e 12 minuti. Ma per un input di lunghezza doppia x=64, l’algoritmo A esegue (nel caso peggiore) 64

operazioni (in circa 52 giorni), ma l’algoritmo B ne esegue 2

(in circa 585.000 anni !!!).

E’ anche poi vero che un algoritmo di complessità polinomiale può essere egualmente “intrattabile”

ed avere tempi di esecuzione molto alti, anche per input di taglia non eccessiva: se per esempio T

(x)= kx

(con k costante reale >0, t numero naturale) allora T

(x) ha ordine polinomiale O(x

) quindi A ha complessità polinomiale, ma se la costante k è per esempio k=10

oppure l’esponente t è t=10000, il numero di operazioni elementari eseguite dall’algoritmo è “astronomico”

(e quindi lo è il tempo di esecuzione) anche per input di taglia x non molto grande.

Complessità di alcuni algoritmi aritmetici.

a) Costruiamo un algoritmo A=Somma(n,m) per calcolare la somma n+m di due numeri naturali

n,m dati in input: supponiamo che x=L(n),y=L(m) siano le lunghezze binarie degli addendi, e che si

abbia x y (in modo che x=max(x,y) sia la taglia dell’input, cioè l’argomento della funzione T

(x)).

L’algoritmo di somma si può eseguire con gli stessi metodi che si usano per sommare numeri naturali rappresentati in base 10, utilizzando però le operazioni elementari di somma sui singoli bits.

Gli steps sono dunque i seguenti:

- si incolonna la rappresentazione binaria di m sotto quella di n, aggiungendo (se la lunghezza x è strettamente maggiore della lunghezza y) un numero (x-y) di bits=0 alla sinistra dei bits di m

- si inizializza il valore del riporto c=0

- procedendo da destra verso si sinistra si somma ogni bit di n con il bit dello stesso posto di m (con l’operazione elementare BitSum di somma di bits), ottenendo ad ogni passo una delle cifre binarie di n+m e un nuovo valore del riporto c

- se l’ultimo riporto è c=1 si aggiunge a sinistra un ulteriore bit=1 nel risultato n+m Alla fine si esce con output n+m.

Per esempio se n=55=(110111)

, m=12=(1100)

(quindi x=L(n)=6, y=L(m)=4) allora:

( 1 1 1 0 0 0 )  (riporto ad ogni somma di bits) 1 1 0 1 1 1+  (bits dell’addendo n)

0 0 1 1 0 0  (bits dell’addendo n) 1 0 0 0 0 1 1  (bits della somma n+m)

dunque il risultato della somma è x+y=(1000000)

=67 . Schematizzando gli steps dell’algoritmo:

1) input n=(a

a

…..a

a

)

, m=(b

b

…..b

b

)

con x=L(n)  y=L(m) 2) se x>y si pone b

=b

=…=b

=0

3) si inizializza c=0

4) per i=0,1…,x-1 si calcola BitSum(a

,b

,c)=(t,c

) e si pone z

=t (bit della somma n+m), c=c

(valore aggiornato del carry)

5) se c=0 (ultimo carry) si esce con output n+m=(z

…..z

z

)

; se invece c=1 si esce con output n+m=(1z

…..z

z

)

Come si vede, oltre ad operazioni trascurabili (come la scrittura di bits), in tale algoritmo si eseguono (nel ciclo dell’istruzione 4)) x operazioni elementari, dunque T

(x)=x e l’algoritmo ha complessità polinomiale (lineare).

b) Costruiamo un algoritmo A=Diff(n,m) per calcolare la differenza n-m di due numeri naturali n,m (con n>m in modo che la differenza n-m sia un numero naturale) dati in input: se x=L(n),y=L(m) sono rispettivamente le lunghezze binarie, si avrà certamente xy (in modo che x=max(x,y) ed x sarà dunque l’argomento della funzione T

(x)).

Si può ricondurre il caso a quello dell’algoritmo Somma(n,m) con il seguente ragionamento:

consideriamo il numero binario m

ottenuto da m sostituendo ogni bit 0 con 1 e ogni bit 1 con 0 e poi aggiungendo a sinistra un numero (x-y) di bits =1 (osserviamo che m

è allora un numero di lunghezza x tale che la somma m+m

nella sua rappresentazione binaria abbia tutti i suoi x bits =1 cioè m+m

=2

-1).

Si ha dunque m+(m

+1)=2

(si dice anche che m

+1 è il “complemento a 2 del numero m”) da cui:

n-m=[n+(m

+1)]-2

.

Per ottenere la differenza n-m basta allora sommare n con il complemento a 2 di m e poi sottrarre 2

al risultato. Esaminiamo la complessità di tale algoritmo:

- costruire m

comporta solo la scrittura di alcuni bits =1 quindi è trascurabile

- calcolare m

+1 (complemento a 2 del numero m) comporta la somma di due addendi dei quali il maggiore (che è m

) ha lunghezza x, dunque comporta x operazioni elementari con l’algoritmo Somma(m

,1)

- il numero (m

+1) ha lunghezza x (infatti per le regole sulla lunghezza della somma si ha L(m

+1)=x oppure L(m

+1)=x+1, ma m

+1=2

-m<2

quindi la seconda possibilità si esclude) dunque per calcolare la somma n+(m

+1) (addendi di lunghezza x) si eseguono x operazioni elementari (con l’algoritmo Somma(n, m

+1))

- la somma n+(m

+1) ha lunghezza x+1 (essendo x la lunghezza degli addendi, la sua lunghezza può essere x oppure x+1 ma n+(m

+1) = n-m+2

> 2

dunque la prima possibilità è esclusa); pertanto sottrarre 2

da n+(m

+1) equivale ad elidere l’ultimo bit =1 a sinistra nel numero n+(m

+1), quindi è trascurabile

Si conclude allora che il numero di operazioni elementari eseguite dall’algoritmo é T

(x)=x+x=2x, ossia che O(T

(x))=O(x) e anche questo algoritmo ha complessità polinomiale (lineare).

c) Costruiamo un algoritmo A=Prod(n,m) per calcolare il prodotto nm di due numeri naturali n,m dati in input: supponiamo che x=L(n),y=L(m) siano le lunghezze binarie degli addendi, e che si abbia x y (in modo che x=max(x,y) ed x sarà dunque l’argomento della funzione T

(x)).

L’algoritmo di prodotto si può eseguire con gli stessi metodi “scolastici” che si usano per moltiplicare numeri naturali rappresentati in base 10: si moltiplica il numero n per ogni cifra del numero m (per le cifre =0 si salta questo passaggio) shiftando ad ogni passo a sinistra il risultato di tale prodotto (per esempio formalmente aggiungendo alcune bits =0 a destra) e infine si sommano tali prodotti per ottenere il risultato finale. Il vantaggio di utilizzare la rappresentazione binaria, e quindi solo le cifre 0,1, consiste nel fatto che il prodotto di n per 1 (unica cifra binaria non nulla) non comporta un vero calcolo ma solo una “copia” del numero n, ed è quindi trascurabile nel calcolo della complessità.

Vediamo un esempio: siano dati n=(1011011)

, m=(101011)

(quindi x=L(n)=7,y=L(m)=6) e calcoliamo il prodotto nm seguendo i vari passi dell’algoritmo:

1 0 1 1 0 1 1 x 1 0 1 0 1 1

1 0 1 1 0 1 1  (si moltiplica n per l’ultima cifra 1 di m, ricopiando n) 1 0 1 1 0 1 1 x

1 0 1 0 1 1

1 0 1 1 0 1 1  (si moltiplica n per la penultima cifra 1 di m, ricopiando n, ma shiftato 1 0 1 1 0 1 1 0 a sinistra di 1 posizione, con l’aggiunta di 1 bit =0 a destra )

1 0 1 1 0 1 1 x 1 0 1 0 1 1

1 0 1 1 0 1 1  (si dovrebbe moltiplicare n per la terzultima cifra 0 di m, ma essendo 0 1 0 1 1 0 1 1 0 il risultato, questo passo si salta, e si moltiplica n per la quartultima 1 0 1 1 0 1 1 0 0 0 cifra 1 di m, ricopiando n, ma shiftato a sinistra di 3 posizioni, con l’aggiunta di 3 bits =0 a destra )

1 0 1 1 0 1 1 x 1 0 1 0 1 1

1 0 1 1 0 1 1  (si dovrebbe moltiplicare n per la quintultima cifra 0 di m, ma questo

1 0 1 1 0 1 1 0 passo si salta, e si moltiplica n per la quartultima cifra 1 di m,

1 0 1 1 0 1 1 0 0 0 ricopiando n, ma shiftato a sinistra di 5 posizioni, con l’aggiunta di

1 0 1 1 0 1 1 0 0 0 0 0 5 bits =0 a destra )

Per ottenere il risultato finale si dovrebbero ora sommare i 4 numeri ottenuti nelle 4 righe. A tale scopo possiamo usare l’algoritmo Somma(n,m), che permette di sommare 2 numeri alla volta:

sommiamo la prima riga con la seconda, poi sommiamo il risultato con la terza riga ed infine sommiamo il risultato con la quarta riga.

L’esempio può essere utile per calcolare la complessità dell’algoritmo: gli unici passi non trascurabili sono quelli in cui si sommano le righe (2 alla volta) utilizzando più volte l’algoritmo Somma. Il caso peggiore si ha quando le righe sono il maggior numero possibile (al massimo il numero delle righe è y) e precisamente quando nessuna cifra di m è =0 (di modo che nessun passo viene saltato) e quando x=y, di modo che il numero di righe sia =x. In questo caso, se le righe sono i numeri a

, a

, …., a

si dovranno sommare a 2 a 2 utilizzando più volte l’algoritmo Somma:

z

=Somma(a

, a

), z

=Somma(z

, a

), z

=Somma(z

, a

),………., z

=Somma(z

, a

) e l’output dell’algoritmo sarà nm = z

.

Le lunghezze delle righe sono crescenti (perché si aggiungono bits =0 a destra):

L(a

)=x, L(a

)=x+1, L(a

)=x+2,…., L(a

)=x+x-1=2x-1

Ricordando la regola della lunghezza della somma, si avrà (nel caso peggiore):

L(z

)=x+1, L(z

)=x+2, L(z

)=x+3,…., L(z

)=x+x-1=2x-1

Dunque (ricordando quanto sappiamo sull’algoritmo Somma) il numero di operazioni elementari eseguite dall’algoritmo (nel caso peggiore) sarà:

T

(x) = (x+1)+(x+2)+(x+3)+ …. + (2x-1)= x(x-1)+(1+2+3+….+(x-1))=

= x(x-1)+(x-1)x/2 = (3x

-3x)/2 (polinomio di 2° grado in x)

Si può concludere che O(T

(x))=O(x

), e che l’algoritmo ha complessità polinomiale (quadratica).

Osservazione. L’algoritmo Prod(n,m) illustrato sopra per calcolare il prodotto di due numeri naturali non è il più efficiente: esiste un algoritmo più sofisticato (che non illustreremo: cfr.

Prop.2.5.13 del libro di testo) che ha complessità O(x

) dove t =log

(3)= 1,58….<2

(dunque di complessità strettamente < O(x

)).

Comunque, per i nostri scopi, sarà sufficiente tener conto dell’algoritmo sopra illustrato, di complessità quadratica.

Esistono anche algoritmi ancora più efficienti per calcolare il prodotto di due numeri naturali, come mostra il seguente risultato (che non dimostreremo):

comunque dato un numero reale  >0 esiste un algoritmo per calcolare il prodotto di 2 numeri naturali che ha complessità ≤ O(x

).

Spesso in seguito, come in questo caso, ci limiteremo a costruire un algoritmo “efficiente” (quindi

di complessità polinomiale) che risolva un problema, senza indagare se sia in effetti il più efficiente

in termini di complessità.