Teoria dei numeri e Crittografia: lezione del 17 ottobre 2011 Aritmetica dei numeri naturali.

Teoria dei numeri e Crittografia: lezione del 17 ottobre 2011 Aritmetica dei numeri naturali.

Nell’insieme Z dei numeri interi relativi supporremo note le operazioni aritmetiche (somma, differenza, prodotto) e le loro proprietà principali (per esempio le proprietà associativa e commutativa di somma e prodotto, la proprietà distributiva della somma rispetto al prodotto);

supporremo inoltre noto l’ordinamento dei numeri interi relativi e le sue proprietà principali.

Assumeremo fra le proprietà dell’insieme N dei numeri naturali anche 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).

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 qualunque numero naturale n

(non necessariamente =1) : 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

” (la dimostrazione di questa versione è simile a quella illustrata sopra).

Esiste anche una versione riferita ad un predicato P(n) in cui la variabile n non assume tutti i valori naturali, ma solo i valori naturali n n

(dove n

è un naturale fissato) e in questo caso l’ipotesi 2) diventa “P(n) vero  P(n+1) vero per ogni n n

”, e la tesi diventa “P(n) è vero per ogni n n

” (anche di questa versione la dimostrazione è simile).

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 arbitraria n

, o

valide per un numero finito di valori di n n

(dove n

è un naturale fissato).

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 altre versioni del Principio di induzione (I

e II

forma) 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 dunque 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 si può eseguire con l’algoritmo Diff di complessità lineare O(x), questo algoritmo della divisione ha complessità di ordine O(x

), cioè 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à uguale a quella di A.

Per esempio, per quanto detto nella lezione precedente, esiste un algoritmo che calcola la divisione (con quoziente e resto) di 2 numeri naturali, e che ha complessità di ordine 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à 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. Per ogni i≥0 ,

essendo r

≥0, si avrebbe q

=bq

+r

≥ bq

>q

(perché b>1), quindi q

>q

. Potremmo allora

costruire l’insieme S che contiene tutti i quozienti q

delle divisioni effettuate: essendo per assurdo

tali quozienti tutti non nulli, S sarebbe un insieme di numeri naturali, senza elemento minimo, 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 l’indice n-1 sia il minimo per cui il quoziente q

=0):

a=bq

+r

q

,r

0 r

<b (q

>0) q

=bq

+r

q

,r

0 r

<b (q

>0) q

=bq

+r

q

,r

0 r

<b

…….

…….

…….

(q

>0) q

=bq

+r

q

,r

0 r

<b (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 ha un dividendo ≤a (perché a=bq

+r

>q

>q

>…>q

) e si può dunque effettuare con l’algoritmo Div di ordine O(x

): la complessità totale dell’algoritmo è di ordine O(x

) .

Divisori e massimo comune divisore.

Dati i numeri naturali a,b diremo che b è divisore di a (equivalentemente che a è multiplo di b) e

scriveremo il simbolo bïa, se esiste un numero intero relativo c tale che a=bc (notare che c è

necessariamente un numero naturale, essendo a,b>0; inoltre da c1 segue necessariamente ab).

Dati a,bN , per testare se bïa basta effettuare la divisione di a per b, calcolare quoziente q e resto r, e verificare se r=0: si ha infatti bïa  r=0 ( è ovvia;  deriva dall’osservazione che se a=bc=bc+0=bq+r, si ha r=0, per l’unicità del resto).

Quindi il test di divisibilità per i numeri naturali si può effettuare con l’algoritmo Div di complessità O(x

) (se x=L(a), con a b: ovviamente se a<b è certamente falso che bïa).

Dati i numeri naturali a,b chiameremo massimo comune divisore di a,b un numero naturale d tale che dïa, dïb (cioè d è divisore comune di a,b) e inoltre d è multiplo di tutti i numeri naturali divisori comuni di a,b.

La seconda proprietà garantisce che d è il più grande dei numeri naturali divisori comuni di a,b ed in particolare è unico (se esiste): scriveremo allora d=mcd(a,b).

Teorema dell’esistenza del mcd(a,b):

Comunque dati i numeri naturali a,b esiste d=mcd(a,b).

Dimostrazione.

Consideriamo l’insieme di tutti i numeri naturali che sono “combinazioni lineari” di a,b a coefficienti interi relativi: S={c / c>0, c=ax+by, x,yZ}.

Tale insieme è non vuoto (almeno a=a1+b0S): sia d il minimo in S.

In particolare d=ax+by, per opportuni x,yZ.

Verifichiamo che d =mcd(a,b).

Per verificare se dïa dividiamo a per d, ottenendo quoziente q e resto r tali che a=dq+r, con r<d, e dimostriamo che r=0. Se per assurdo fosse r>0, sarebbe r=a-dq=a(1-xq)+b(-yq)S, contraddizione (perché r<d e d è il minimo in S).

Analogamente si verifica che dïb.

Se inoltre d

è un numero naturale divisore comune di a,b allora esistono numeri naturali s,t tali che d

s=a, d

t=b, da cui d=ax+by=d

(sx+ty) cioé d

è divisore di d.

Nota: nella dimostrazione precedente si è anche notato che d=mcd(a,b) è una combinazione lineare della forma d=ax+by, per opportuni coefficienti interi relativi x,yZ . Tali coefficienti x,y non sono però univocamente determinati: per esempio per ogni intero relativo k si ha:

ax+by=a(x+kb)+b(y-ka).

Due numeri naturali a,b sono detti coprimi o relativamente primi se mcd(a,b)=1, o equivalentemente se 1 è l’unico loro divisore comune.

Proprietà elementari:

1) Se 1=ax+by è combinazione lineare di a,b con coefficienti interi relativi x,y, allora a,b sono coprimi.

Basta infatti ricordare che il mcd(a,b) è la minima delle combinazioni lineari >0 di a,b, quindi certamente 1=mcd(a,b).

2) Due numeri naturali consecutivi a, b=a+1 sono sempre coprimi.

Basta osservare che 1=a(-1)+b1 e applicare la 1).

3) Dividendo due numeri naturali a,b per il loro massimo comune divisore d=mcd(a,b) si ottengono due numeri naturali coprimi.

Infatti posto d=ax+by (con x,y interi relativi), si ha 1=(a/d)x+(b/d)y, e applicando la 1) si ottiene che a/d, b/d sono coprimi.

4) Dati 3 numeri naturali a,b,c, se aï(bc) e se a,b sono coprimi allora aïc.

Infatti, posto bc=ad, con dN, ed 1=mcd(a,b)=ax+by, con x,yZ, si ha c=acx+bcy=a(cx+dy).

5) Dati 3 numeri naturali a,b,c, se aïc, bïc, e se a,b sono coprimi allora (ab)ïc .

Infatti, posto c=ar=bs, con r,s N, ed 1=mcd(a,b)=ax+by, con x,yZ, si ha c=acx+bcy=ab(sx+ry).

Lemma:

Dati 2 numeri naturali a,b ed effettuata la divisione con a=dividendo, b=divisore : a=bq+r q,r0 r<b

si ha:

1) se r=0 (equivalentemente se bïa) allora mcd(a,b)=b 2) se r>0 allora mcd(a,b)=mcd(b,r)

Dimostrazione.

La dimostrazione di 1),2) segue facilmente dalla definizione di massimo comune divisore.

Illustriamo un algoritmo per calcolare d=mcd(a,b), dati i numeri naturali a,b: è il cosiddetto algoritmo Euclideo delle divisioni successive.

Esso consiste nei seguenti passi:

1) Si divide a per b trovando quoziente e resto

2) Si effettuano successive divisioni con il seguente criterio: ogni volta che una divisione ha resto non nullo, si effettua una successiva divisione prendendo come dividendo e divisore rispettivamente divisore e resto della precedente divisione. L’algoritmo si ferma quando si ottiene una divisione con resto nullo

3) Il resto (non nullo) della penultima divisione è il mcd(a,b).

Schematizzando l’algoritmo:

a=bq

+r

(q

0, 0<r

<b) b=r

q

+r

(q

0, 0<r

<r

) r

=r

q

+r

(q

0, 0<r

<r

) .

.

r

=r

q

+r

(q

0, 0<r

<r

) r

=r

q

+r

(q

0, r

=0)

Output: r

=mcd(a,b)

Prima di tutto osserviamo che l’algoritmo si ferma dopo un numero finito di divisioni : infatti la successione dei resti è decrescente, e se per assurdo si ottenessero sempre resti >0, il loro insieme sarebbe un sottoinsieme di N senza minimo, contro l’assioma del minimo.

Inoltre l’affermazione che r

=mcd(a,b) si può dimostrare applicando più volte il precedente Lemma:

mcd(a,b)=mcd(b,r

)=mcd(r

,r

)=….=mcd(r

,r

)=r

.

Calcoleremo in seguito la complessità dell’algoritmo Euclideo: poiché ogni passo dell’algoritmo

consiste in una divisione è ovvio che sia necessario dare una stima (nel caso peggiore) del numero n

delle divisioni effettuate nell’algoritmo. A tale scopo ci serviremo della teoria dei numeri di

Fibonacci.