Teoria dei numeri e Crittografia: lezione del 4 aprile 2011

(1)

Teoria dei numeri e Crittografia: lezione del 4 aprile 2011

Dimostreremo ora che, dati 2 numeri naturali a,b con a>b, il numero n di divisioni effettuate nell’algoritmo Euclideo è  log



a (parte intera del logaritmo di a avente per base il numero d’oro), e inoltre tale maggiorazione è ottimale, cioè per opportune scelte dei valori di a,b il numero delle divisioni è proprio = log



a (dunque questo è effettivamente il caso peggiore).

Siano a,b numeri naturali, con a>b. Effettuiamo le n divisioni successive dell’algoritmo Euclideo:

a=bq

1

+r

1

(q

1

0, 0<r

1

<b) b=r

1

q

2

+r

2

(q

2

0, 0<r

2

<r

1

) r

1

=r

2

q

3

+r

3

(q

3

0, 0<r

3

<r

2

) .

. .

r

n-3

=r

n-2

q

n-1

+r

n-1

(q

n-1

0, 0<r

n-1

<r

n-2

) r

n-2

=r

n-1

q

n

+r

n

(q

n

0, r

n

=0)

r

n-1

=mcd(a,b)

Per costruzione si ha :

a > b > r

1

> r

2

> …….. > r

n-1

> 0=r

n

dunque i quozienti q

i

sono tutti non nulli (se fosse q

i

=0 si avrebbe r

i-2

=r

i-1

q

i

+r

i

, da cui r

i-2

=r

i

, contraddizione perché r

i-2

<r

i-1

<r

i

); in particolare ogni quoziente q

i

è 1.

Poniamo per omogeneità di indici r

0

=b (in modo che la prima e la seconda divisione siano rispettivamente a=r

0

q

1

+r

1

, r

0

=r

1

q

2

+r

2

) e dimostriamo che si ha:

*(****) r*

n-j

 F

j+1

per ogni j=1,2,…,n Ragioniamo per induzione (II

^a

forma).

Per j=1 si ha (essendo r

n-1

>0) : r

n-1

 F

2

= 1.

Sia j>1: supponiamolo vero per ogni k<j, e dimostriamolo vero per j.

Essendo vero in particolare per k=j-1,j-2, si ha:

r

n-j+1

 F

j

, r

n-j+2

 F

j-1

Ricavando il resto r

n-j

dalla divisione numero n-j+2 si ha (tenendo conto che q

n-j+2

1):

r

n-j

= r

n-j+1

q

n-j+2

+r

n-j+2

 r

n-j+1

+r

n-j+2

 F

j

+ F

j-1

= F

j+1

come si voleva.

*In particolare, applicando la (****) per j=n, n-1, si ha:*

b = r

0

 F

n+1

r

1

 F

n

e dalla prima divisione (essendo q

1

1) a=r

0

q

1

+r

1

 r

0

+r

1

F

n+1

+F

n

=F

n+2

.

*Ma dalla (***) segue aF*

n+2

>

ⁿ

, da cui log



(a)>n, dunque n  log



a .

Tale maggiorazione è ottimale nel senso che per opportuni valori di a,b il numero n delle divisioni è proprio = log



a .

Precisamente poniamo a=F

n+2

, b=F

n+1

e , ricordando le eguaglianze che legano i numeri di Fibonacci, osserviamo che le divisioni dell’algoritmo Euclideo in questo caso sono le seguenti:

F

n+2

= F

n+1

1+F

n

(q

1

=1 , r

1

=F

n

) F

n+1

= F

n

1+F

n -1

(q

2

=1 , r

2

=F

n-1

) .

.

F

4

= F

3

1+F

2

(q

n-1

=1 , r

n-1

=F

1

=1=mcd(F

n+2

,F

n+1

))

(2)

F

3

= 2 = F

2

2+0 (q

n

=2, r

n

=0)

quindi le divisioni sono in numero di n (abbiamo incidentalmente anche dimostrato che 2 numeri di Fibonacci consecutivi sono coprimi perché mcd(F

n+1

, F

n+2

)=1).

Ricordando che, per la (***), si ha:

F

n+1

< 

ⁿ

< F

n+2

< 

ⁿ⁺¹

< F

n+3

Si ricava che :

n < log



(F

n+2

) = log



a < n+1

quindi n è proprio la parte intera del numero reale log



a , ossia n= log



a in questo caso particolare.

Da quanto precede si deduce che, dati 2 numeri naturali a,b con a>b, se n é il numero di divisioni effettuate nell’algoritmo Euclideo per il calcolo del mcd(a,b), si ha n log



(a) (dove  é il numero d’oro).

Se x=L(a), y=L(b) si ha necessariamente xy ed inoltre:

2

^x-1

 a < 2

^x

da cui log

2

(a) < x, n log



(a) = log



(2)log

2

(a) < (log



(2))x.

Essendo log



(2) una costante, il numero n delle divisioni dell’algoritmo Euclideo è perciò di ordine

 O(x).

Ricordando che ogni divisione effettuata nell’algoritmo coinvolge numeri  a, quindi di lunghezza

 x, e si può effettuare perciò con l’algoritmo Div di complessità  O(x

²

), si ottiene che globalmente l’algoritmo Euclideo delle divisioni successive ha complessità  O(x

³

).

Nota: con un ragionamento più raffinato (che omettiamo) che considera l’ordine di grandezza (decrescente) dei numeri coinvolti nelle successive divisioni, si può dimostrare che in effetti l’algoritmo Euclideo delle divisioni successive ha complessità  O(x

²

).

Possiamo trovare anche un’altra interessante maggiorazione per il numero n di divisioni dell’algoritmo Euclideo, stavolta in funzione del minore b fra i 2 numeri a,b.

Abbiamo già notato che, se n è il numero di divisioni nell’algoritmo Euclideo, si ha:

b F

n+1

(dove F

i

indica il generico termine della successione di Fibonacci) ma sappiamo anche che:



^n-1

< F

n+1

dunque 

^n-1

< b, ossia (estraendo il logaritmo in base 10):

(n-1)log

10

() < log

10

(b)

Poiché log

10

()  0,206 > 1/5 si ottiene (n-1) < 5log

10

(b) , n < 5log

10

(b)+1 Se t=L(b)

10

è il numero di cifre nella rappresentazione di b in base 10 si ha : 10

^t-1

 b< 10

^t

e dunque log

10

(b) < t, da cui n<5t+1, ossia n  5t.

In pratica quindi il numero di divisioni nell’algoritmo Euclideo non è superiore al quintuplo del numero di cifre (nella rappresentazione in base 10) del più piccolo dei numeri a,b.

Per esempio se a>b e se b (in base 10) ha 100 cifre, il numero di divisioni dell’algoritmo Euclideo

non è superiore a 500, qualunque sia il numero di cifre di a.