Teoria dei numeri e Crittografia: lezione del 27 aprile 2011 Teorema.
Se m,n>1 sono numeri naturali coprimi si ha (mn) = (m)(n) (dove è funzione di Eulero).
Dimostrazione:
Definiamo la funzione f: Zmn Zm x Zn ponendo f([x]mn) = ([x]m , [x]n) .
La f è surgettiva: infatti per ogni coppia ([a]m ,[b]n) Zm x Zn il Teorema Cinese del Resto assicura l’esistenza di qualche soluzione intera del sistema:
(mod ) (mod )
x a m
x b n
e si ha f([x]mn) = ([x]m , [x]n)= ([a]m , [b]n).
Avendo dominio e codominio stessa cardinalità mn, la f è biunivoca.
Si può verificare che una classe [a]mn è invertibile in Zmn se e solo se la classe [a]m é invertibile in Zm e la classe [a]n é invertibile in Zn : infatti se [a]mn[b]mn=[ab]mn=[1]mn allora ab1 (mod mn) da cui ab1 (mod m) e ab1 (mod n) ossia [a]m[b]m=[ab]m=[1]m e [a]n[b]n=[ab]n=[1]n ; viceversa se [a]m[b]m=[ab]m=[1]m e [a]n[c]n=[ac]n=[1]n allora ab1 (mod m) e ac1 (mod n) ma il Teorema Cinese del Resto assicura l’esistenza di un intero d tale che db (mod m) e dc (mod n), da cui ad1 (mod m) e ad1 (mod n), m(ad-1), n(ad-1), mn(ad-1) (perché m, n sono coprimi) e si conclude che [a]mn[d]mn=[ad]mn=[1]mn .
Dunque la restrizione di f al gruppo Zmn* fornisce una funzione biunivoca fra Zmn* e Zm*x Zn* , per cui si conclude che (mn) = Zmn* = Zm*x Zn*= Zm* Zn*= (m)(n) .
Osservazione. Il Teorema precedente si può estendere facilmente per induzione al caso di più di 2 numeri naturali: se m1,m2,….,mn sono numeri naturali >1 a 2 a 2 coprimi, si ha:
(m1m2…mn)= (m1) (m2)… (mn).
Basta infatti procedere per induzione con base n=2 utilizzando (come nella dimostrazione del Teorema Cinese del Resto) l’osservazione che se m1,m2,….,mn, mn+1 sono a 2 a 2 coprimi anche (m1m2….mn), mn+1 sono coprimi, dunque se (m1m2…mn)= (m1) (m2)… (mn) allora:
(m1m2…mnmn+1)= ((m1m2…mn)mn+1)= (m1m2…mn)(mn+1)= (m1) (m2)… (mn)(mn+1).
Sia n>1 un numero naturale. Per il Teorema di Fattorizzazione Unica possiamo fattorizzare in modo unico n nel prodotto di numeri primi, e se raccogliamo sotto forma di potenza i fattori primi uguali, possiamo fattorizzare n in prodotto di potenze di primi distinti:
n = p p1k1 2k2....prkr con pi primi distinti, ki interi >0 , tutti univocamente determinati.
Conoscendo la fattorizzazione di n, si può facilmente calcolare la funzione di Eulero (n).
Infatti si può notare che due potenze di primi distinti ph, qk sempre sono numeri coprimi: se per assurdo fosse d=mcd(ph,qk)>1, considerato un divisore primo p0 di d si avrebbe p0ph, p0qk, dunque (essendo p0 primo) p0p, p0q e infine p0=p=q, contraddizione.
Basta allora applicare il Teorema precedente e la formula per il calcolo della funzione di Eulero per le potenze di primi per ricavare:
(n) = (p1k1) ( p2k2).... ( prkr)=p1k1-1(p1-1)p2k2-1(p2-1)....prkr-1(pr-1)
La formula precedente, con semplici passaggi algebrici, si può trasformare nella seguente:
(n) = n(1-1/p1)(1-1/p2)…..(1-1/pr)
La formula precedente fornisce anche un algoritmo per calcolare la funzione di Eulero di n, conoscendo la fattorizzazione di n in prodotto di primi: per calcolare la complessità di tale algoritmo, si può notare che si tratta di calcolare il prodotto di fattori pi , (pi-1) tutti n (quindi tutti di lunghezza x=L(n)), ed inoltre il numero dei fattori è k1+k2+….+kr x-1 (perché n =
1 2
1k 2k .... rkr
p p p 2 2 ....2k k1 2 kr =2k k1+ 2....+kr ed x=L(n) è il massimo intero tale che 2x-1 n dunque k1+k2+….+kr+1 x); come sappiamo dalle considerazioni fatte sulla complessità delle operazioni aritmetiche, tale calcolo si può fare con un algoritmo di complessità non più che polinomiale (rispetto ad x).
Per avere però la complessità dell’algoritmo “globale” che, dato in input un intero n>1, calcoli la sua funzione di Eulero, si dovrebbe sommare anche la complessità di un algoritmo che calcoli i fattori primi di n: attualmente però, come già detto, non esiste un algoritmo di complessità non più che polinomiale che risolva il problema della fattorizzazione, quindi la formula precedente non ci permette di trovare globalmente un algoritmo di complessità non più che polinomiale per calcolare la funzione di Eulero di n.
Potrebbe naturalmente esistere un algoritmo di complessità non più che polinomiale che, dato un naturale n>1 in input, calcoli la funzione di Eulero (n), senza calcolare i fattori primi di n: tuttavia a tutt’oggi non esiste un algoritmo di questo tipo (e i matematici dubitano che esista).
Anzi molti matematici sono convinti che sia vera la seguente congettura: esiste un algoritmo di complessità non più che polinomiale che risolva il problema della fattorizzazione di n in prodotto di primi esiste un algoritmo di complessità non più che polinomiale che calcola la funzione di Eulero (n) (l’implicazione è vera per le considerazioni precedenti).
Ad avvalorare tale congettura, si può notare che essa è vera nel caso in cui n=pq sia prodotto di 2 primi distinti p, q (caso che ritroveremo nel sistema crittografico RSA).
Infatti, se supponiamo che esista un algoritmo di complessità non più che polinomiale che, dato in input n>1, calcola la funzione di Eulero (n) = (p-1)(q-1)= pq-(p+q)+1, è possibile calcolare, con complessità non più che polinomiale, anche la somma p+q=pq-(n)+1=n-(n)+1, da cui, impostando un classico sistema somma-prodotto è possibile ricavare i valori dei fattori p, q come soluzioni di un’equazione di secondo grado x2-(p+q)x+pq = 0 con coefficienti tutti di lunghezza x=L(n) e tali soluzioni si possono calcolare con un algoritmo ancora di complessità non più che polinomiale (come vedremo in seguito….).
Il seguente risultato permette di ricondurre il calcolo di (n) al calcolo dei (d) con d<n:
Teorema.
Per ogni naturale n>1 si ha n =
n dn d
d
1
)
(
(e in particolare (n)=n -
n dn d
d
1
)
( ).
Dimostrazione:
Sia A = { dN / dn }. E’ facile verificare che la funzione f: A A definita da f(d)=n/d è iniettiva, quindi biunivoca perché A è finito.
Per ogni dA sia Ad = { xN / 1xn , mcd(x,n)=d }: tale insieme è non vuoto perché dAd .
Al variare di dA gli insiemi Ad formano una partizione di {1,2….,n}: ogni elemento x{1,2….,n}
appartiene a qualche Ad (basta scegliere d=mcd(x,n)) e ovviamente, se c,dA sono distinti, gli insiemi Ad, Ac non hanno elementi comuni (se xAdAc si avrebbe d=mcd(x,n)=c).
Si deduce allora che n = {1,2,….,n}= d
d A
A
Fissato dA, sia Bd = { xN / 1xn/d ; x, n/d coprimi }. Definiamo la funzione g : Ad Bd
ponendo g(x)=x/d (notare che x/dBd in quanto x/d, n/d sono coprimi perché d=mcd(x,n)).
Tale funzione è biunivoca: l’iniettività è banale, mentre per la surgettività basta osservare che se yBd, allora x=ydAd (è facile verificare che dall’ipotesi y, n/d coprimi segue che mcd(x,n)=d) e dunque g(x)=y.
Si conclude allora che Ad=Bd= (n/d).
Sfruttando la funzione biunivoca f. A A definita sopra, si ha che A=f(A)={ n/d / dA }, da cui per la proprietà commutativa della somma di interi:
n = d
d A
A
= d
d A
B
= ( / )
d A
n d
= ( ( ))
d A
f d
= ( )
d A
d
e si ha la tesi.
Algoritmo per il calcolo della parte intera della radice n-esima
Sia dato il numero naturale a (radicando), e, fissato un numero naturale n>1, costruiamo un algoritmo che, dati in input a, n calcoli la parte intera di na, ossia il più grande numero naturale y tale che yn a.
Supponendo x=L(a), si ha 2x-1 a<2x .
Se n x allora 2n2x>a dunque na< 2, e la parte intera della radice n-esima di a è =1.
Possiamo allora supporre n<x .
Rappresentiamo a in base 2, e raggruppiamo le sue x cifre binarie in k blocchi di cifre:
a = 12……k
dove ogni i è un blocco di n cifre binarie (aggiungiamo eventualmente degli zeri a sinistra per rendere anche il primo blocco 1 di n cifre): tratteremo ogni blocco i come un valore numerico intero 0 (rappresentato in base 2).
Si ha ovviamente 0 i<2n per ogni i, essendo ogni i un blocco di n cifre binarie (quindi, come valore numerico, di lunghezza binaria n ). Inoltre certamente almeno 1 è >0.
Descriviamo il seguente algoritmo che genera 2 successioni di numeri interi 0:
yi , xi (con i=0,1,…,k) 1) Si pone y0=x0=0
2) Per i=1,….,k si ripete il seguente blocco di istruzioni (che calcola il valore yi in funzione del valore precedente yi-1):
a) Si calcola la massima cifra binaria {0,1} tale che (2yi-1+)n 2nxi-1+i
b) Si pone yi=2yi-1+, xi=2nxi-1+i
Alla fine l’algoritmo esce con output “yk = parte intera di na”.
Esaminando l’algoritmo si vede che ad ogni iterazione nel passo 2) il numero xi si ottiene shiftando verso sinistra il numero xi-1 di n posizioni, e aggiungendo alla sua destra il blocco i : quindi, partendo dal valore iniziale x0=0, è ovvio che alla fine del ciclo si avrà:
xk=12……k = a.
D’altro canto il numero yi si ottiene shiftando verso sinistra il numero yi-1 di 1 posizione e aggiungendo alla sua destra la cifra binaria trovata nel passo a): quindi, partendo dal valore iniziale y0=0, è ovvio che le varie cifre binarie trovate in successione nella iterazione della a) sono proprio le cifre binarie dell’output yk .
Inoltre ad ogni iterazione, esaminando le istruzioni a),b), si nota che yinxi (esaminare l’istruzione a)) e quindi in particolare ykn xk=x.
Dimostriamo inoltre che per ogni i=1,2,…,k si ha:
(yi+1)n > xi (*) Ragioniamo per induzione (Ia forma).
Per i=1 (*) è vero, perché il valore della cifra nella a) è in questo caso =1 (in quanto (2y0+1)n=1 2nx0+1=1 perché, come già notato, si ha 1>0) dunque y1=2y0+1=1, x1=2nx0+1=1 , 1n=11.
Supponiamo (*) vero per i, e dimostriamolo vero per i+1.
Dunque supponiamo che (yi+1)n > xi , e dimostriamo che (yi+1+1)n > xi+1 .
Se nell’iterazione i+1 al passo a) il valore della cifra è 0 (quindi se (2yi+1)n>2nxi+i+1 ) allora la tesi è ovvia perché appunto yi+1=2yi+=2yi, xi+1=2nxi+i , (yi+1+1)n=(2yi+1)n>2nxi+i+1 = xi+1 . Se invece nell’iterazione i+1 il valore della cifra è 1, e se fosse per assurdo (yi+1+1)n xi+1 , si avrebbe:
yi+1=2yi+=2yi+1, xi+1=2nxi+i , (yi+1+1)n=(2yi+2)n=2n(yi+1)n xi+1=2nxi+i
da cui:
2n[(yi+1)n-xi] i
ed essendo per l’ipotesi induttiva (yi+1)n-xi 1, si avrebbe 2n i , in contraddizione con l’osservazione iniziale che ogni blocco i ha valore numerico < 2n .
In particolare da (*) per i=k si ottiene:
(yk+1)n > xk = x
Poiché avevamo già osservato che ykn xk=a , possiamo concludere che l’output yk è effettivamente il più grande numero naturale y tale che la yn a , quindi yk è la parte intera di na.
Resta da esaminare la complessità di calcolo di tale algoritmo, in funzione di x=L(a).
Le uniche vere operazioni sono eseguite nel passo 1) a), quando si deve calcolare la potenza:
(2yi-1+)n= yin
(le altre operazioni si riducono a degli shift con inserimento di cifre binarie in coda, oppure al confronto di numeri binari per decidere il valore di , e si possono considerare trascurabili).
La potenza yin si può calcolare eseguendo n-1 prodotti della forma yi j-1yi con j=1,…,n-1 (prodotti in cui entrambi i fattori sono yin ykn=a): ognuno di tali prodotti si può eseguire con un algoritmo di complessità O(x2). Ricordando, come detto all’inizio, che siamo nell’ipotesi n<x, il numero di tali prodotti è <x, dunque il calcolo della potenza yin si può eseguire con un algoritmo di complessità O(x3).
Infine il passo 1) a) dell’algoritmo viene eseguito k volte, dove k è il numero dei blocchi (di n cifre binarie ciascuno) in cui sono state divise le x cifre binarie di a: si ha perciò k<x e complessivamente l’algoritmo ha complessità di ordine O(x4) dove x è la lunghezza binaria del radicando a.
