5 5 5 5

(1)

Teoria dei numeri e Crittografia: lezione del 19 ottobre 2011 La successione di Fibonacci.

La successione dei numeri di Fibonacci è la successione di numeri naturali F

n

(n>0) definita ponendo: F

1

=F

2

=1, F

n

=F

n-1

+F

n-2

per ogni n >2

Quindi F

3

=2; F

4

=3, F

5

=5, F

6

=8 etc…

Tale successione interviene in molti problemi combinatori.

Esempio. Per ogni naturale n, il numero delle parole di lunghezza n sull’alfabeto {0,1} che non contengono 2 bits =1 consecutivi è F

n+2

.

Per dimostrarlo basta usare la seconda forma del principio di induzione.

Per n=1 l’affermazione è banale: sono 2=F

3

le parole in questione (le parole 0 e 1).

Sia n>1: supponiamo vera l’affermazione per ogni numero naturale k<n e dimostriamola per n.

Consideriamo una generica parola w di lunghezza n che non contiene 2 bits consecutivi =1.

Distinguiamo 2 casi:

1) se l’ultimo bit di w è 0, la parola w si ottiene da una parola di lunghezza n-1 (che non contiene 2 bits consecutivi =1) aggiungendo come ultimo bit 0. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di F

n+1

2) se l’ultimo bit è 1, la parola w si ottiene da una parola di lunghezza n-2 (che non contiene 2 bits consecutivi =1) aggiungendo come penultimo bit 0 e come ultimo bit 1. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di F

n

In totale il numero di valori di w è F

n

+F

n+1

=F

n+2

.

Problema: trovare una formula algebrica per il calcolo del generico numero di Fibonacci F

n

. A tale scopo ricordiamo alcune classiche nozioni geometriche.

Se AB è un segmento di estremi A,B è di lunghezza a (con a reale >0), si chiama parte aurea di AB un segmento AC (dove C è un punto interno ad AB) tale che la lunghezza x di AC sia media proporzionale fra a e la lunghezza (a-x) del segmento CB:

a : x = x : (a-x)

e da ciò si ricava x

²

+ax-a

²

= 0, da cui x = a(-1

⁵

)/2.

Essendo x>0, l’unico valore accettabile è x = a(-1+

5

)/2, da cui si ottiene il valore del rapporto:

a/x = 2/(-1+

⁵

)=(

⁵

+1)/21,61

(è il cosiddetto rapporto aureo o numero d’oro, indicato spesso con la lettera greca ).

Il concetto di parte aurea di un segmento ha molte applicazioni geometriche: per esempio il lato del decagono regolare ha la stessa lunghezza della parte aurea del raggio della circonferenza circoscritta.

Descriviamo alcune proprietà del numero d’oro :

1) Nel ragionamento precedente, poiché x è soluzione di x

²

+ax-a

²

= 0, dividendo per x

²

si ottiene che  = a/x soddisfa l’identità:

1 +  - 

²

= 0 da cui:



²

= 1+ ()* 2) Si ricava anche:

(1-)

²

= 1-2+

²

e tenendo conto di (*) si ottiene:

(1-)

²

*= 2- (**)*

Il numero d’oro ha una stretta relazione con la successione dei numeri di Fibonacci F

n

.

(2)

Calcolando le potenze di base  ad esponente naturale e confrontandole con alcuni valori di F

n

, osserviamo che:

F

2

=1 < 

¹

1,61 < F

3

=2 < 

²

2,6 < F

4

=3 < 

³

4,2 < F

5

=5 e si può congetturare che si abbia :

F

n+1

< 

ⁿ

< F

n +2

*(***) per ogni naturale n.*

Possiamo dimostrare che ciò è vero, ragionando per induzione (II

^a

forma). Per n=1 abbiamo già notato che (***) è vero.

*Sia n>1: supponiamolo vero per tutti i k<n, e dimostriamolo vero per n; poiché (***) è in* particolare vero per k=(n-1),(n-2), si ha F

n

< 

^{n -1}

< F

n +1

, F

n-1

< 

^{n -2}

< F

n

, da cui, sommando, si ha:

F

n+1

= F

n

+F

n-1

< 

^{n –1}

+ 

^{n –2}

< F

n+1

+F

n

= F

n+2

Ma dalla (**) segue che:



^{n –1}

+ 

^{n –2}

= 

^{n –2}

(1+) = 

ⁿ

*quindi la (***) é vera per n.*

Dimostriamo ora la seguente formula algebrica per il calcolo del generico numero di Fibonacci:

F

n

= [

ⁿ

– (1-)

ⁿ

]/

⁵

per ogni naturale n.

Ragioniamo di nuovo per induzione (II

^a

forma). Per n=1 si ha:

[ – (1-)]/

⁵

= (2-1) /

⁵

= 1 = F

1

Sia n>1: supponiamo la formula vera per ogni k<n e dimostriamola per n; poiché è vera in particolare per k=(n-1),(n-2), si ha:

F

n-1

= [

^n-1

– (1-)

^n-1

]/

⁵

, F

n-2

= [

^n-2

– (1-)

^n-2

]/

⁵

e sommando si ottiene (tenendo conto di (*) e (**)):

F

n-1

+ F

n-2

= F

n

= [

^n-2

(1+) - (1-)

^n-2

(2-)]/

⁵

= [

ⁿ

– (1-)

ⁿ

]/

⁵

come si voleva.

In effetti la formula ottenuta per il calcolo dei numeri di Fibonacci è poco utile, perché coinvolge numeri irrazionali.

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.

(3)

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

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 r

n-1

=F

1

=1=mcd(F

n+2

,F

n+1

) ossia che 2 numeri di Fibonacci consecutivi sono coprimi).

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.

Riassumendo: 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 (per definizione di lunghezza binaria):

2

^x-1

 a < 2

^x

da cui log

2

a < x, n log



a = log



2log

2

a < kx (dove k= log



2 è una costante) Si conclude che il numero n delle divisioni dell’algoritmo Euclideo di ordine O(x).

Ricordando che ogni divisione effettuata nell’algoritmo coinvolge dividendi tutti  a (quindi di lunghezza  x), e si può effettuare perciò con l’algoritmo Div complessità di ordine O(x

²

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

³

) polinomiale (cubica).

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

²

).

(4)

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.

5 5 5 5

Teoria dei numeri e Crittografia: lezione del 19 ottobre 2011 La successione di Fibonacci.

La successione dei numeri di Fibonacci è la successione di numeri naturali F

(n>0) definita ponendo: F

=F

=1, F

=F

+F

per ogni n >2

Quindi F

=2; F

=3, F

=5, F

=8 etc…

Tale successione interviene in molti problemi combinatori.

Esempio. Per ogni naturale n, il numero delle parole di lunghezza n sull’alfabeto {0,1} che non contengono 2 bits =1 consecutivi è F

.

Per dimostrarlo basta usare la seconda forma del principio di induzione.

Per n=1 l’affermazione è banale: sono 2=F

le parole in questione (le parole 0 e 1).

Sia n>1: supponiamo vera l’affermazione per ogni numero naturale k<n e dimostriamola per n.

Consideriamo una generica parola w di lunghezza n che non contiene 2 bits consecutivi =1.

Distinguiamo 2 casi:

1) se l’ultimo bit di w è 0, la parola w si ottiene da una parola di lunghezza n-1 (che non contiene 2 bits consecutivi =1) aggiungendo come ultimo bit 0. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di F

2) se l’ultimo bit è 1, la parola w si ottiene da una parola di lunghezza n-2 (che non contiene 2 bits consecutivi =1) aggiungendo come penultimo bit 0 e come ultimo bit 1. Per l’ipotesi induttiva i valori di w in questo caso sono in numero di F

In totale il numero di valori di w è F

+F

=F

.

Problema: trovare una formula algebrica per il calcolo del generico numero di Fibonacci F

. A tale scopo ricordiamo alcune classiche nozioni geometriche.

Se AB è un segmento di estremi A,B è di lunghezza a (con a reale >0), si chiama parte aurea di AB un segmento AC (dove C è un punto interno ad AB) tale che la lunghezza x di AC sia media proporzionale fra a e la lunghezza (a-x) del segmento CB:

a : x = x : (a-x)

e da ciò si ricava x

+ax-a

= 0, da cui x = a(-1

)/2.

Essendo x>0, l’unico valore accettabile è x = a(-1+

)/2, da cui si ottiene il valore del rapporto:

a/x = 2/(-1+

)=(

+1)/21,61

(è il cosiddetto rapporto aureo o numero d’oro, indicato spesso con la lettera greca ).

Il concetto di parte aurea di un segmento ha molte applicazioni geometriche: per esempio il lato del decagono regolare ha la stessa lunghezza della parte aurea del raggio della circonferenza circoscritta.

Descriviamo alcune proprietà del numero d’oro :

1) Nel ragionamento precedente, poiché x è soluzione di x

+ax-a

= 0, dividendo per x

si ottiene che  = a/x soddisfa l’identità:

1 +  - 

= 0 da cui:



= 1+ (*) 2) Si ricava anche:

(1-)

= 1-2+

e tenendo conto di (*) si ottiene:

(1-)

= 2- (**)

Il numero d’oro ha una stretta relazione con la successione dei numeri di Fibonacci F

.

Calcolando le potenze di base  ad esponente naturale e confrontandole con alcuni valori di F

, osserviamo che:

F

=1 < 

1,61 < F

=2 < 

2,6 < F

=3 < 

4,2 < F

=5 e si può congetturare che si abbia :

F

< 

< F

(***) per ogni naturale n.

Possiamo dimostrare che ciò è vero, ragionando per induzione (II

forma). Per n=1 abbiamo già notato che (***) è vero.

Sia n>1: supponiamolo vero per tutti i k<n, e dimostriamolo vero per n; poiché (***) è in particolare vero per k=(n-1),(n-2), si ha F

< 

< F

, F

= 1+ ()* 2) Si ricava anche:

*= 2- (**)*

*(***) per ogni naturale n.*

*Sia n>1: supponiamolo vero per tutti i k<n, e dimostriamolo vero per n; poiché (***) è in* particolare vero per k=(n-1),(n-2), si ha F

*quindi la (***) é vera per n.*