Teoria dei numeri e Crittografia: lezione del 30 marzo 2011

Teoria dei numeri e Crittografia: lezione del 30 marzo 2011

L’algoritmo Prod(n,m) illustrato nella lezione precedente 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à < 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à non più che polinomiale) che risolva un problema, senza indagare se sia in effetti il più efficiente in termini di complessità.

Aritmetica dei numeri naturali.

Nell’insieme N dei numeri naturali (ossia dei numeri interi >0) supporremo note le proprietà elementari delle operazioni aritmetiche (somma, differenza, prodotto) e dell’ordinamento.

Ricordiamo fra le proprietà dell’insieme N dei numeri naturali il cosiddetto Assioma del buon ordinamento (o del minimo): in un qualunque sottoinsieme S non vuoto di N esiste sempre un numero naturale minimo sS (cioè tale che s≤x per ogni xS).

E’ ovvio che la stessa proprietà vale anche per ogni sottoinsieme non vuoto S di N{0}, in quanto se S contiene 0, allora 0 è il minimo in S.

Principio di induzione (I

forma):

Sia P(n) una proprietà relativa ad un generico numero naturale n (si dice anche che P(n) è un predicato nella variabile n, con n che assume valori in N).

Se:

1) P(1) è vero

2) per ogni n : P(n) vero  P(n+1) vero allora P(n) è vero per ogni nN.

Dimostrazione.

Per assurdo sia non vuoto l’insieme S di tutti i naturali n tali che P(n) è falso, e sia s il minimo in S.

Allora s>1 (per l’ipotesi 1)), dunque s-1N, e poiché s-1<s si ha s-1S, dunque P(s-1) è vero, ossia P(s) è vero (per l’ipotesi 2)), contraddizione.

Il numero 1 è detto anche base dell’induzione.

Esistono altre versioni dello stesso principio in cui la base dell’induzione può essere un fissato numero naturale n

: in tale caso l’ipotesi 1) diventa “P(n

) è vero”, l’ipotesi 2) diventa “P(n) vero

 P(n+1) vero per ogni nn

”, la tesi diventa “P(n) è vero per ogni naturale nn

”.

Esiste anche una versione del principio di induzione riferita ad un predicato P(n) in cui la variabile

n non assume tutti i valori naturali, ma solo i valori consecutivi 1, 2, …, n

(dove n

è un naturale

fissato) e in questo caso l’ipotesi 2) diventa “P(n) vero  P(n+1) vero per ogni n=1,….,n

-1”, e la

tesi diventa “P(n) è vero per ogni n=1,2,….,n

” .

Principio di induzione (II

forma):

Sia P(n) una proprietà relativa ad un generico numero naturale n.

Se:

1) P(1) è vero

2) per ogni n>1 : P(k) vero per tutti i k<n  P(n) vero allora P(n) è vero per ogni nN.

Dimostrazione.

Per assurdo sia non vuoto l’insieme S di tutti i naturali n tali che P(n) è falso, e sia s il minimo in S.

Allora s>1 (per l’ipotesi 1)), e poiché 1,2,…,s-1<s, si ha 1,2,…,s-1S, P(1), P(2), ……, P(s-1) sono veri, e si deduce (per l’ipotesi 2)) che P(s) è vero, contraddizione.

Anche per questa forma del principio esistono altre versioni con base dell’induzione qualunque, o valide per un numero finito di valori di n.

Notiamo anche che l’Assioma del minimo vale anche per un qualunque sottoinsieme non vuoto S di N{0} (insieme dei numeri interi non negativi) perché se S contiene 0 allora 0 è il minimo in S, mentre nel caso contrario S è sottoinsieme di N, e dunque esiste il minimo in S per l’Assioma del minimo valido in N.

Da ciò seguono altrettante versioni del Principio di induzione per l’insieme N{0} (in cui la “base”

dell’induzione è 0 e non 1).

Teorema dell’algoritmo della divisione per i numeri naturali:

Dati comunque i naturali a,b (a=”dividendo”, b=”divisore”), esistono e sono unici i numeri interi q,r0 (q=”quoziente”, r=”resto”) tali che a=bq+r, con r<b (si dice anche che si è effettuata la

“divisione di a per b”).

Dimostrazione.

Esistenza di q,r: Sia S={x0 / x=a-by, con y intero 0}. Poiché a=a-b0S, tale S è sottoinsieme non vuoto di N{0}, e sia s il minimo in S. Si ha s0, s=a-by, con y intero 0, a=by+s. Se poniamo q=y, r=s, avremo la tesi se dimostreremo che s<b: se per assurdo fosse sb, si avrebbe s-b0, da cui s-b=a-b(y+1)S, s-b<s, contraddizione.

Unicità di q,r: Supponiamo a=bq+r=bq

+r

con q,q

,r,r

interi 0, r,r

<b, e sia per esempio r r

. Allora r-r

0, b>rr-r

=b(q

-q), quindi 0≤q

-q<1, q

-q=0, q

=q (unicità del quoziente). Da ciò si deduce anche r-r

=b(q

-q)=0, ossia r=r

(unicità del resto).

Dimostreremo ora che è possibile trovare quoziente e resto della divisione fra due numeri naturali, con un algoritmo di complessità polinomiale.

Se a=dividendo, b=divisore , possiamo assumere che sia ab (se a<b la divisione di a per b si effettua in modo banale con quoziente q=0, resto r=a).

Per quanto riguarda le lunghezze binarie si ha allora certamente x=L(a) y=L(b).

La divisione di a per b si può effettuare con l’usuale algoritmo “scolastico” che chiameremo Div(a,b): il vantaggio di utilizzare cifre binarie 0,1 consiste (come nel caso dell’algoritmo del prodotto) nel fatto che la moltiplicazione di un numero per 1 (unica cifra binaria non nulla) dà come risultato una “copia” del numero stesso.

Facciamo un esempio: siano a=(1101101)

, b=(101)

.

Prima “stacchiamo” (da sinistra) nel divisore a un “segmento” binario (di lunghezza minima) che

(come valore numerico in base 2) sia  b (in questo caso è il segmento 110 di lunghezza 3) e

sottraiamo da tale segmento il valore del divisore b , dando nello stesso tempo il valore 1 al primo

bit del quoziente q:

1101101 101

101 1  primo bit del quoziente q 1  differenza fra il segmento 110 e b=101 In seguito “abbassiamo” il prossimo bit del dividendo accostandolo alla differenza ottenuta, ma poiché in questo caso otteniamo un numero 11 inferiore al divisore, diamo il valore 0 al secondo bit del quoziente q e “abbassiamo” un ulteriore bit ottenendo il numero 111 non inferiore al dividendo: diamo allora il valore 1 al terzo bit del quoziente e sottraiamo dal numero 111 così ottenuto il valore del divisore b: 1101101 101

101 101

111

101

10

Di nuovo “abbassiamo” il prossimo bit del dividendo, ma poiché otteniamo un numero 100 inferiore al divisore, diamo il valore 0 al quarto bit del quoziente q e “abbassiamo” un ulteriore bit ottenendo il numero 1001 non inferiore al divisore b: diamo allora il valore 1 al quinto bit del quoziente e sottraiamo dal numero 1001 così ottenuto il valore del divisore b: 1101101 101

101 10101

111

101

1001

101

100

Avendo ottenuto un valore 100 che è inferiore al divisore (sarà il resto), l’algoritmo si ferma con output quoziente q=(10101)

, e resto r=(100)

.

Nel caso generale, se x=L(a)y=L(b), l’algoritmo illustrato sopra esegue un numero (non superiore ad x) di sottrazioni fra coppie di numeri (di lunghezza ≤ x=L(a)), e poiché ognuna di tali sottrazioni ha (come visto nell’algoritmo Diff) complessità lineare O(x), questo algoritmo della divisione ha complessità ≤O(x

), cioè al più quadratica (quindi è anch’esso un algoritmo “efficiente”).

L’algoritmo Div(a,b) (illustrato sopra con un esempio) si può formalizzare nei dettagli nel modo che esporremo ora.

Se x=L(a) poniamo:

a=a

2

+a

2

+…..+a

2

+a

2

dove ogni a

=0,1, a

=1 .

In output avremo le cifre binarie del quoziente q = q

2

+q

2

+…..+q

2

+q

2

(non è detto che il quoziente abbia esattamente lunghezza x, perché durante il calcolo alcune delle prime cifre q

potranno essere =0) e il resto r<b.

L’algoritmo esegue i seguenti passi:

1) Si pone b

=1

2) Si esegue un ciclo di x-1 iterazioni, per i=1,….,x-1 nel modo seguente:

se bb

allora si pone q

=1, b

=2(b

-b)+a

; se b>b

si pone q

=0, b

=2b

+a

(tale ciclo definisce le cifre q

,….,q

, e costruisce dei numeri ausiliari b

,…,b

; notare che in ogni caso si ha per costruzione b

=2(b

-bq

)+a

ad ogni iterazione)

3) Infine se bb

si pone q

=1, r=b

-b; se invece b>b

si pone q

=0, r=b

(questo passo costruisce l’ultima cifra q

del quoziente q e il resto r; notare che in ogni caso per costruzione si ha r=b

-bq

)

4) Si esce con output: quoziente q = q

2

+q

2

+…..+q

2

+q

2

e resto r .

Posto q= q

2

+q

2

+…..+q

2

+q

2

, dobbiamo verificare che 0r<b, e che a=bq+r.

Si verifica per induzione che per ogni i=1,2,….,x si ha:

b

=(a

2

+a

2

+…+a

2

+a

2

)-b(q

2

+q

2

+…+q

2

). (*) Infatti per i=1 si ha b

=1=a

, quindi la (*) è vera.

Supponendo vera la (*) per i, dimostriamola per i+1:

b

=b

=2(b

-bq

)+a

=(a

2

+a

2

+…+a

2

+a

2

)-b(q

2

+q

2

+…+q

2

) La (*) in particolare per i=x implica:

b

=(a

2

+a

2

+…..+a

2

+a

2

)-b(q

2

+q

2

+…+q

2

) da cui:

r=b

-bq

=(a

2

+a

2

+…..+a

2

+a

2

)-b(q

2

+q

2

+…+q

2

+q

2

)=a-bq . Inoltre si verifica anche per induzione che per ogni i=1,2,….,x si ha:

0b

<2b . (**)

Infatti per i=1 si ha 0b

=1<2b (perché b>0), dunque la (**) è vera.

Supponendo vera la (**) per i, dimostriamola per i+1.

Seguendo l’algoritmo si deduce che:

- se bb

allora si ha b

=2(b

-b)+a

0 (essendo (b

-b),a

0), e inoltre b

=2(b

-b)+a

2(2b-1-b)+a

=2b+(a

-2)<2b (essendo a

=0,1) ; - se invece b>b

allora si ha b

=2b

+a

0 (essendo b

,a

0) e inoltre b

=2b

+a

2(b-1)+ a

=2b+(a

-2)<2b (come sopra)

e in ogni caso la (**) è vera per i+1.

La (**) in particolare per i=x implica:

0b

<2b

Da ciò possiamo dedurre che 0r<b: infatti nell’istruzione 3) vi sono 2 casi e in ambedue verificheremo la tesi:

- se bb

allora si pone r=b

-b, dunque banalmente r0, ma anche r<b perché b

<2b - se b>b

allora si pone r=b

, dunque r<b ed inoltre r0 perché b

0.

Nota. E’ interessante citare il seguente risultato (che non dimostreremo):

comunque dato un algoritmo A che calcola il prodotto di 2 numeri naturali, esiste un algoritmo B che calcola la divisione (con quoziente e resto) di 2 numeri naturali, e che ha complessità non superiore a quella di A.

Per esempio, per quanto detto in precedenza, esiste un algoritmo che calcola la divisione (con quoziente e resto) di 2 numeri naturali, e che ha complessità ≤ O(x

) dove t =log

(3): ma anche in questo caso, nelle considerazioni che seguono ci accontenteremo di sfruttare il fatto che per risolvere un tale problema esiste un algoritmo di complessità non superiore alla quadratica.

Rappresentazione di un numero naturale in una generica base b>1.

È un’applicazione del teorema dell’algoritmo della divisione per i numeri interi.

Fissiamo un numero naturale a ed un numero naturale b>1 (detto “base”). Applicando l’algoritmo

della divisione, operiamo una divisione, con a come dividendo, b come divisore, ottenendo

l’esistenza di due interi q

, r

, entrambi ≥0, tali che a=bq

+r

, con r

<b. Se il quoziente q

0 (cioè q

>0) operiamo un’altra divisione, prendendo q

come dividendo, b come divisore e ottenendo l’esistenza di due interi q

, r

, entrambi ≥0, tali che q

=bq

+r

, con r

<b. Ancora, se il quoziente q

0 (cioè q

>0), operiamo una terza divisione, prendendo q

come dividendo, b come divisore, ottenendo l’esistenza di due interi q

, r

, entrambi ≥0 tali che q

=bq

+r

, con r

<b; se q

0 (cioè q

>0) si ripete ancora il procedimento. In pratica tale procedimento continua con una successiva divisione solo se il quoziente della precedente divisione è non nullo: nella successiva divisione il dividendo coincide con il quoziente della divisione precedente, mentre il divisore rimane costantemente =b.

Il procedimento si arresta quando si perviene ad una divisione con quoziente nullo.

Dimostriamo che questo algoritmo ha termine dopo un numero finito di divisioni.

Per assurdo supponiamo di operare infinite divisioni tutte con quoziente non nullo. Essendo b>1, si ha bq

>q

, ed essendo r

≥0, si ha q

=bq

+r

≥ bq

>q

, quindi q

>q

. Per induzione si dimostra facilmente che in generale si avrebbe q

>q

, per ogni numero naturale n .

Potremmo allora costruire l’insieme S che contiene tutti i quozienti q

, q

,….. delle divisioni effettuate: essendo per assurdo tali quozienti tutti non nulli, sarebbe un insieme di numeri naturali, senza elemento minimo (perché q

>q

, per ogni numero naturale n) in contraddizione con l’Assioma del minimo.

Possiamo quindi affermare con certezza che dopo un numero finito di divisioni, perverremo ad una divisione con quoziente =0, e l’algoritmo ha termine.

Elenchiamo le divisioni effettuate (supponendo che il numero di tali divisioni sia n, e che dunque il quoziente q

di indice n-1 sia nullo):

a=bq

+r

q

,r

0 r

<b (se q

>0) q

=bq

+r

q

,r

0 r

<b (se q

>0) q

=bq

+r

q

,r

0 r

<b

…….

…….

…….

(se q

>0) q

=bq

+r

q

,r

0 r

<b (se q

>0) q

=bq

+r

q

=0 r

<b.

Operando delle sostituzioni successive si ottiene:

a=bq

+r

=b(bq

+r

)+r

=b

q

+br

+r

=b

(bq

+r

)+br

+r

=b

q

+b

r

+br

+r

=………=

=b

q

+b

r

+…..+ b

r

+br

+r

=b

r

+ b

r

+…..+ b

r

+br

+r

La scrittura ottenuta:

a=r

b

+r

b

+…..+r

b

+r

b+r

è detta rappresentazione di a in base b ed i numeri r

,r

,r

,…r

sono detti cifre della rappresentazione (notare che sono univocamente determinati, per l’unicità di quoziente e resto nella divisione). Come si nota nel procedimento precedente, le cifre r

,r

,r

,…r

(essendo resti delle divisioni per b) sono numeri interi ≥0 e <b, cioè i possibili valori delle cifre sono compresi fra i numeri interi 0,1,…,b-1 , dove b è la base fissata.

Il simbolo usato per la rappresentazione di a in base b é a=(r

r

……r

r

r

)

.

Notiamo anche che la cifra r

è ≠0 : infatti se per assurdo fosse =0, sarebbe q

=r

=0, contraddizione (perché l’indice n-1 è per costruzione il minimo per cui il relativo quoziente è nullo).

Si deduce anche che il numero di divisioni n coincide con la lunghezza di a in base b:

n = L(a)

Calcoliamo la complessità dell’algoritmo che calcola (dati in input i numeri naturali a, b con b>1)

la rappresentazione di a in base b (ovviamente al termine dell’algoritmo saranno fornite in output le

cifre della rappresentazione di a in base b , rappresentate ognuna in base 2).

Supponiamo ab (se a<b, la rappresentazione di a in base b è banale con unica cifra a). Si ha allora certamente x=L(a) ≥ y=L(b).

Utilizzando l’algoritmo esposto sopra, essendo n = L(a)

(dove n è il numero divisioni), si ha 2

≤ b

≤a (perché 2≤b)

dunque n≤x (perché x è il massimo intero tale che 2

≤a). Ogni divisione è effettuata con un

dividendo ≤a e si può effettuare con l’algoritmo Div di ordine ≤O(x

), quindi la complessità totale

dell’algoritmo è di ordine ≤O(x

) .