Teoria dei numeri e Crittografia: lezione del 28 marzo 2011 Complessità di alcuni algoritmi aritmetici a)

Teoria dei numeri e Crittografia: lezione del 28 marzo 2011 Complessità di alcuni algoritmi aritmetici

a) Nella lezione precedente abbiamo costruito un algoritmo Somma(n.m) che calcola la somma n+m di due numeri naturali n, m dati in input. Il suo schema è il seguente:

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 3)) x operazioni elementari (dove x è la lunghezza maggiore dei due addendi), dunque T

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

Per le considerazioni che faremo sulla complessità dei prossimi algoritmi, è 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:

2

 a < 2

2

 b < 2

segue:

2

< 2

+2

 a+b< 2

+2

 2

+2

= 2

2

2

= 2

 ab< 2

2

= 2

e ricordando che L(a+b)=s è il più grande dei numeri naturali che soddisfano 2

 a+b, mentre L(ab)=t è il più grande dei numeri naturali che soddisfano 2

 ab, si conclude che k s< k+2, e che k+h-1  t < k+h+1, ossia la 1) e la 2).

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).