Teoria dei numeri e Crittografia: lezione del 28 aprile 2011

(1)

Teoria dei numeri e Crittografia: lezione del 28 aprile 2011

Nella lezione scorsa abbiamo costruito un algoritmo che, dati in input i numeri naturali a, n (con n>1) fornisce in ouput la parte intera di ⁿa: esso ha complessità  O(x⁴) dove x=L(a).

Osservazione: nell’istruzione in cui si calcola la massima cifra binaria {0,1} tale che:

(2yi-1+)ⁿ 2ⁿxi-1+i

ovviamente si deve verificare che la diseguaglianza vale almeno per =0 (altrimenti il valore di  non sarebbe calcolabile):

(*) (2yi-1)ⁿ 2ⁿxi-1+i (per ogni i=1,….,k) La (*) si può dimostrare usando l’induzione (I^a forma).

Per i=1 la (*) è vera in quanto (2y0)ⁿ=0 2x0+1=1. Supponiamo vera la (*) per i e dimostriamola vera per i+1.

Ricordiamo che per costruzione yi=2yi-1+, xi=2ⁿxi-1+i dove (2yi-1+)ⁿ 2ⁿxi-1+i . Si ha allora:

(2yi)ⁿ=2ⁿ(2yi-1+)ⁿ 2ⁿ(2ⁿxi-1+i) 2ⁿxi  2ⁿxi+i+1 (essendo i+10) dunque la (*) è vera per i+1.

L’algoritmo precedente (per il calcolo della parte intera di ⁿa) si può trasformare facilmente in un algoritmo che risponda al quesito: dati in input i numeri naturali a, n (con n>1) il numero a coincide con la potenza di esponente n di un opportuna base intera ? (per esempio potremmo eseguire un test per decidere se a è un quadrato perfetto, un cubo perfetto etc…..).

Infatti basta calcolare con l’algoritmo precedente la parte intera yk diⁿa, ed verificare se essa coincida esattamente con ⁿa: quindi basta aggiungere all’algoritmo una istruzione che esegua il calcolo della potenza ykn e verifichi se il risultato è =a : in caso affermativo a è una potenza n-esima esatta di base naturale (e la base è proprio yk), in caso negativo non lo é.

Tale algoritmo ha anch’esso complessità  O(x⁴): infatti si deve aggiungere all’algoritmo precedente solo il calcolo della potenza ykn che, come visto nella lezione precedente quando si esaminava il calcolo delle potenze yin , ha complessità  O(x³) .

Infine possiamo notare che si può costruire un algoritmo che risponda al quesito: dato in input un numero naturale a, il numero a coincide con la potenza di esponente n di un opportuna base intera, per un opportuno esponente intero n>1 (notare che n non è fissato a priori).

Infatti (tranne nel caso banale a=1) un eventuale valore dell’esponente n>1 (se esiste) è certamente

<x=L(a) (come già notato nella lezione precedente, se n x allora la parte intera di ⁿa è =1 quindi in tale caso a è potenza n-esima di base naturale solo per a=1): quindi basta ripetere l’algoritmo precedente per tutti gli n con 2 n<x: se per nessuno di tali valori il test dà esito positivo, possiamo concludere con certezza che l’input a non è potenza di un opportuna base intera, per nessun esponente n>1; se invece per qualcuno di tali valori n il test dà esito positivo, abbiamo trovato che per quel valore dell’esponente n il numero a è potenza di un opportuna base intera.

Poiché l’algoritmo precedente ha complessità di ordine  O(x⁴) ed esso viene ripetuto (nel caso peggiore) un numero x-2 di volte, complessivamente questo algoritmo ha complessità polinomiale di ordine  O(x⁴(x-2))=O(x⁵).

Algoritmo per la soluzione di sistema somma-prodotto.

Supponiamo che p, q siano due numeri naturali di cui si conoscono somma a=p+q, e prodotto n=pq.

Costruiamo un algoritmo per calcolare, dati in input a, n, i valori di p, q.

Se x=L(n), si ha a n tranne nel caso banale p=q=1: infatti se pq2 si ha a=p+q2ppq=n . Se dunque supponiamo a n si ha L(a) x.

(2)

E’ ben noto che p, q sono soluzioni dell’equazione di secondo grado:

x² – ax + n = 0 dunque (se p q):

p =( a+²d )/2, p =( a-²d )/2 dove d = a²- 4n.

In tale algoritmo, tranne le moltiplicazioni per 4 e le divisioni per 2 (che si ottengono con semplici aggiunte o cancellazioni di cifre binarie 0 a destra), le uniche operazioni significative sono il calcolo di d = a²- 4n, l’estrazione di ²d , la somma (o differenza) di a e ²d .

Il calcolo di a² si può eseguire con un algoritmo di complessità  O(x²); poiché L(a²)  2L(a)  2x, L(4n)=2+L(n)=2+x, il calcolo di d = a²- 4n si può eseguire con un algoritmo di complessità O(x);

poiché L(d)  L(a²)  2x, il calcolo di ²d (che sarà per ipotesi un numero naturale quindi coinciderà con la sua parte intera) si può eseguire con un algoritmo di complessità  O((2x)⁴)=

O(x⁴) (vedere paragrafo precedente); infine il calcolo della la somma (o differenza) di a e ²d si potrà eseguire con un algoritmo di complessità  O(x).

In totale il calcolo dei numeri p,q si potrà eseguire con un algoritmo di complessità  O(x⁴) : ciò completerà le considerazioni fatte in precedenza sulla funzione di Eulero e la fattorizzazione unica.

Esponenziazione modulare

Torniamo alla complessità delle operazioni nell’insieme delle classi di congruenza.

Sia m>1 un intero, fissiamo un esponente intero positivo h<m, una classe di congruenza [b]Zm

(possiamo supporre 0b<m), e poniamoci il problema di trovare un algoritmo “efficiente” per calcolare la potenza [b^h] (o equivalentemente la riduzione b^hmodm): sarebbe anche utile che i numeri coinvolti nei calcoli eseguiti dall’algoritmo non fossero “eccessivamente” grandi rispetto ad m.

Esporremo un algoritmo molto efficiente che risolve tale problema, detto esponenziazione modulare.

Siano x=L(m), t=L(h) le lunghezze (binarie) del modulo m e dell’esponente h: essendo h<m si ha tx. Poiché t rappresenta il numero di cifre binarie di h, si ha una rappresentazione della forma:

h=at-12^t-1+ at-22^t-2+….+a12+a0 (con ai=0,1, at-1=1)

Costruiamo una successione y0,y1,...,yt di numeri interi 0 ponendo:

y0=1; per ogni i>0 : yi=₍_y_{i 1}_- ²_b^a^{t i}^- ₎modm

Dimostriamo che tale algoritmo risolve il problema iniziale, poiché fornisce il valore della riduzione b^hmodm: precisamente dimostriamo che si ha yt= b^hmodm.

Dimostriamo prima per induzione che per ogni i con 1 i  t, si ha:

yi  _b⁽^{a 2}^{t 1}^- ^{i 1}^-⁺^{a 2}^{t 2}^- ^{i 2}^-^+…+^. ^a^{t i 1}^-⁺^{2 a}⁺ ^{t i}^-⁾ (mod m) (*)

Si ha y1=(y b₀² ^a^{t 1}^- )modm quindi y1_b^a^{t 1}^- (mod m), e la (*) è vera per i=1.

Supponiamo (*) vera per i e dimostriamola per i+1: si hanno le seguenti congruenze modulo : yi+1  (y b_i² â^{t i 1}^-^- ) _b^{[ (}^{2 a 2}^{t 1}^- ⁱ⁺^{a 2}^{t 2}^- ^{i 1}^-^{+… +}^. â^{t i 1}^-⁺^{2 a}⁺ ^{t i}^-⁾⁺â^{t i 1}^{- -}^]=_b⁽^{a 2}^{t 1}^- ⁱ⁺^{a 2}^{t 2}^- ^{i 1}^-^{+… +}^. ^{a 2 a}^{t i}^- ⁺ ^{t i 1}^{- -}⁾

quindi la (*) è vera per i+1.

In particolare, per i=t, si ottiene la congruenza:

yt  _b⁽^{a 2}^{t 1}^- ^{t 1}^-⁺^{a 2}^{t 2}^- ^{t 2}^-^{+… +}^. ^{a 2 a}¹ ⁺ ⁰⁾= b^k (mod m)

Poiché si ha 0≤ yi<m (ogni elemento della successione yi è una riduzione modulo m) la precedente congruenza implica che yt = x^kmodm.

Calcoliamo la complessità dell’algoritmo.

Come già notato si ha 0 yi<m per ogni i.

(3)

Inoltre ogni elemento della successione yi (con i>0) si può calcolare (a partire dal precedente) nel modo seguente: si calcola il prodotto yi-12= yi-1yi-1 di 2 fattori di lunghezza  x (con un algoritmo di complessità  O(x²)) ottenendo un risultato di lunghezza  L(yi-1)+ L(yi-1)  2x; si moltiplica tale risultato per bat i- (che è un fattore che coincide con b o con 1 poiché l’esponente at-1 è =0,1) con un algoritmo di complessità  O((2x)²)=O(x²) (perché L(b) x) ottenendo un risultato di lunghezza  2x+x = 3x) ; infine si calcola la riduzione modulo m di tale risultato, con un algoritmo di complessità  O((3x)²=O(x²). Dunque il calcolo di ogni elemento della successione yi (con i>0) si può effettuare con un algoritmo di complessità  O(x²).

Osserviamo anche che il numero degli elementi della successione da costruire è tx, dunque complessivamente l’algoritmo ha complessità  O(x³).

Notiamo che nell’algoritmo anche la grandezza dei numeri coinvolti nei calcoli è limitata (rispetto al modulo m): ad ogni passo, nella costruzione di yi , sono coinvolti sempre numeri non superiori ad m³.

Esempio.

Siano m=341, b=2, e calcoliamo [2³⁴⁰] in Z341.

Si tratta quindi di calcolare con l’esponenziazione modulare la riduzione 2³⁴⁰mod341.

La rappresentazione binaria dell’esponente 340 è:

340 = 12⁸+02⁷+12⁶+02⁵+12⁴+02³+12²+02¹+0 = (101010100)2

Seguendo i passi dell’algoritmo, costruiamo la successione y0,y1,y2,y3,y4,y5,y6,y7,y8,y9 con y0=1 e per i>0 : yi=(y_{i 1}_ ²2^a^{9 i}^-)mod341 , dove at-i è la cifra binaria coefficiente di 2^t-i nella rappresentazione di 340.

Si ha, facendo i calcoli:

y1 = 2 ; y2 = 4 ; y3 = 32 ; y4 =1 ; y5 = 2 ; y6 = 4 ; y7 = 32 ; y8 =1 ; y9 = 1 = 2³⁴⁰mod341.

Possiamo allora concludere che [2³⁴⁰]=[1] in Z341.

Osservazione: l’ipotesi che l’esponente h nella esponenziazione modulare sia < m non è restrittiva.

Infatti possiamo dimostrare che:

per ogni esponente naturale k si ha [b^k]= [b^h] per un opportuno h con h<m (*)

Infatti essendo Zm=m fra gli elementi [b⁰],…., [b^m-1], [b^m] ne esisteranno almeno 2 coincidenti, dunque esisteranno interi non negativi r,s m con r>s tali che [b^s]= [b^r].

Dimostriamo la (*): se ks allora è banale (in quanto ks<rm dunque basta porre h=k). Sia dunque k>s: dividiamo (k-s) per (r-s) ottenendo quoziente q e resto t con 0t<r-s

(k-s) = (r-s)q+h

Notiamo che per ogni intero i0 si ha [b^s+(r-s)i]= [b^s] (utilizzando la I^a forma dell’induzione, la tesi è vera banalmente per i=0; se è vera per i allora [bs+(r-s)(i+1)]= [b^s+(r-s)i][b^r-s]= [b^s][b^r-s]= [b^r]= [b^s] quindi è vera anche per i+1).

Dunque nel nostro caso [b^k]=[b^s+(r-s)q][b^t]=[b^s+t] con h=s+t<s+(r-s)=r m, e si ha la tesi.

Dimostriamo alcune proprietà elementari dei gruppi.

Teorema.

Sia G un gruppo (in notazione moltiplicativa).

1) Se a,b,cG, da ac=bc segue a=b (legge di cancellazione a destra); da ca=cb segue a=b (legge di cancellazione a sinistra).

(4)

2) (Lagrange) Se G è commutativo e finito di cardinalità n, per ogni aG il prodotto di n fattori uguali ad a è l’elemento neutro di G: aa….a = 1G (n fattori).

Dimostrazione:

1) Se ac=bc, moltiplicando a destra per l’inverso di c si ha (ac)c^-1=(bc)c^-1, da cui (per la proprietà associativa) a(cc^-1)=b(cc^-1), a1G=b1G , a=b. Analogo ragionamento per l’altra legge.

2) Siano a1,a2,…,an gli elementi distinti di G. Per la legge di cancellazione, gli elementi:

aa1,aa2,…,aan

sono distinti, quindi sono n elementi di G, e dunque esauriscono G:

{ aa1,aa2,…,aan } = G = {a1,a2,…,an } Per la proprietà commutativa si ha:

1G 1 n

i i

a



 

1 1 1

( ) ...

n n n

i i i

a aa aa a a

  

 

  

e per la legge di cancellazione si ha la tesi.

Nota: Si può dimostrare, con altre tecniche, che la 2) del Teorema vale anche nel caso di un gruppo (finito) non commutativo.