Teoria dei numeri e Crittografia: lezione del 14 novembre 2011 Esponenziazione modulare
Torniamo alla complessità delle operazioni nell’insieme delle classi di congruenza.
Cerchiamo di costruire un algoritmo efficiente che, dati in input 3 numeri naturali m, h, b (con m>1) calcoli nell’insieme delle classi di congruenza modulo m la potenza [bh] .
Possiamo supporre (sostituendo eventualmente b con la sua riduzione modulo m) che sia 0 b<m.
Se identifichiamo le classi [0], [1],….,[m-1]con i loro rappresentanti “canonici” 0, 1, …,m-1, lo scopo dell’algoritmo è in pratica quello di calcolare la riduzione bhmodm: oltre all’efficienza dell’algoritmo, sarebbe anche utile che i numeri coinvolti nei calcoli eseguiti dall’algoritmo non fossero “eccessivamente” grandi rispetto ad m.
Supponiamo per il momento che l’esponente h sia <m (vedremo in seguito che tale ipotesi non è restrittiva).
Siano x=L(m), t=L(h) le lunghezze binarie del modulo m e dell’esponente h: da h<m si ha t x.
Un algoritmo poco efficiente che risolva il problema sarebbe ovviamente quello di calcolare la potenza bh (eseguendo h-1 prodotti della forma bib con i=1,….,h-1) e poi calcolare la riduzione bhmodm (eseguendo una divisione per m): il numero di prodotti da calcolare sarebbe però di ordine lineare O(m) rispetto ad m e dunque di ordine esponenziale O(2x) rispetto ad x.
Esporremo invece un algoritmo molto efficiente che risolve tale problema, detto esponenziazione modulare.
Poiché t rappresenta il numero di cifre binarie di h, si ha una rappresentazione della forma:
h=at-12t-1+ at-22t-2+….+a12+a0 (con ai=0,1, at-1=1)
L’algoritmo dell’esponenziazione modulare esegue i seguenti passi:
1) Si costruisce una successione y0,y1,...,yt di numeri interi 0 ponendo:
y0=1; per ogni i>0 yi=(yi 1- 2bat i- )modm 2) Si esce con output yt = bhmodm .
Dimostriamo che in effetti si ha yt= bhmodm.
Dimostriamo prima per induzione che per ogni i con 1 i t, si ha:
yi b(a 2t 1- i 1-+a 2t 2- i 2-+…+. at i 1-+2 a+ t i-) (mod m) (*)
Si ha y1=(y b02 at 1- )modm quindi y1bat 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 bi2 at i 1-- ) b[ (2 a 2t 1- i+a 2t 2- i 1-+… +. at i 1-+2 a+ t i-)+at i 1- -]=b(a 2t 1- i+a 2t 2- i 1-+… +. a 2 at i- + t i 1- -)
quindi la (*) è vera per i+1.
In particolare, per i=t, si ottiene la congruenza:
yt b(a 2t 1- t 1-+a 2t 2- t 2-+… +. a 2 a1 + 0)= bk (mod m)
Poiché si ha 0≤ yi<m per ogni i (perché ogni elemento della successione yi è una riduzione modulo m) la precedente congruenza implica che yt = xkmodm.
Calcoliamo ora la complessità dell’algoritmo dell’esponenziazione modulare.
Come già notato si ha 0 yi<m per ogni i, quindi L(yi) x per ogni i. Inoltre essendo b<m, anche L(b) x.
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à di ordine O(x2)) ottenendo un risultato di lunghezza L(yi-1)+ L(yi-1) 2x; si moltiplica tale risultato per a-
b t i(che è un fattore che coincide con b o con 1 poiché l’esponente at-1 è =0,1)
con un algoritmo di complessità di ordine O((2x)2)=O(x2) (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à di ordine O((3x)2)=O(x2). Dunque il calcolo di ogni elemento della successione yi
(con i>0) si può effettuare con un algoritmo di complessità di ordine O(x2).
Osserviamo anche che il numero degli elementi della successione da costruire è t x (quindi di ordine O(x)) dunque complessivamente l’algoritmo dell’esponenziazione modulare ha complessità polinomiale di ordine O(x3).
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 m3.
Esempio.
Siano m=341, b=2, e calcoliamo [2340] in Z341.
Si tratta quindi di calcolare con l’esponenziazione modulare la riduzione 2340mod341.
La rappresentazione binaria dell’esponente 340 è:
340 = 128+027+126+025+124+023+122+021+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=(yi 1- 22a9 i-)mod341 , dove at-i è la cifra binaria coefficiente di 2t-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 = 2340mod341.
Possiamo allora concludere che [2340]=[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 [bk]= [bh] per un opportuno h con h<m (*)
Infatti essendo Zm=m fra gli elementi [b0],…., [bm-1], [bm] ne esisteranno almeno 2 coincidenti, dunque esisteranno interi non negativi r,s m con r>s tali che [bs]= [br].
Dimostriamo la (*): se ks allora è banale (in quanto ks<rm dunque basta porre h=k). Sia dunque k>s: dividiamo (k-s) per (r-s) ottenendo quoziente q e resto t con 0t<r-s
(k-s) = (r-s)q+h
Notiamo che per ogni intero i0 si ha [bs+(r-s)i]= [bs] (utilizzando la Ia forma dell’induzione, la tesi è vera banalmente per i=0; se è vera per i allora [bs+(r-s)(i+1)]= [bs+(r-s)i][br-s]= [bs][br-s]= [br]= [bs] quindi è vera anche per i+1).
Dunque nel nostro caso [bk]=[bs+(r-s)q][bt]=[bs+t] con h=s+t<s+(r-s)=r m, e si ha la tesi.
Alcune proprietà elementari dei gruppi.
Teorema.
Sia G un gruppo (in notazione moltiplicativa).
1) Se a,b,cG, da ac=bc segue a=b (legge di cancellazione a destra); da ca=cb segue a=b (legge di cancellazione a sinistra).
2) (Lagrange) Se G è commutativo e finito di cardinalità n, per ogni aG 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
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.
Sia G un gruppo (in notazione moltiplicativa). Per ogni aG e per ogni numero naturale k, definiamo la potenza di base a ed esponente k uguale al seguente elemento di G:
ak=aa…a (k fattori).
La 2) dell’ultimo Teorema dimostrato nella lezione precedente si può dunque riformulare nel modo seguente:
se G è gruppo commutativo e finito di cardinalità n, per ogni aG si ha an = 1G . (ripetiamo che la tesi è ugualmente valida nel caso di un gruppo non commutativo).
Dato un elemento a del gruppo G, possiamo estendere il concetto di potenza di base a anche al caso di esponente 0, definendo per convenzione a0=1G .
E’ facile verificare che per le potenze di base a valgono le usuali proprietà delle potenze numeriche:
se h, k sono interi 0 si ha ah+k=ahak, ahk=(ah)k .
Nota: Se la notazione è additiva, invece di potenza parleremo di multiplo di a con coefficiente naturale k, definito come ka=a+a+…+a (k addendi), ponendo poi per convenzione 0a=0A (neutro del gruppo additivo G): le proprietà dimostrate sopra si possono facilmente riformulare nel linguaggio additivo.
Se G è gruppo commutativo finito di cardinalità n, per quanto già dimostrato, esiste qualche numero naturale k tale che ak=1G (per esempio k=n), dunque esiste il minimo numero naturale k tale che ak=1G (detto ordine o periodo dell’elemento a, e indicato con ordG(a), o semplicemente con ord(a)).
Se consideriamo una qualunque potenza di base a ad esponente naturale h, dividendo h per k=
ord(a) con quoziente q e resto r (con 0r<k) si ha ah=akq+r=(ak)qar=(1G)qar=ar, quindi ogni potenza di base a coincide con una delle potenze a0,a1,…,ak-1 .
Inoltre tali potenze sono distinte: se per assurdo fosse as=at con 0t<s<k, si avrebbe (cancellando t fattori con la legge di cancellazione) as-t=1G, con 0<s-t<k, contraddizione perché k=ord(a).
Inoltre una potenza ah coincide con l’elemento neutro 1G se e solo se kh: infatti, ragionando come sopra con la divisione di h per k, si ha ah= ar, dunque se ah=1G si ha r=0 (perché non può essere 0<r<k=ord(a)) e viceversa se r=0 allora ah=a0=1G .
In particolare, poiché si è dimostrato che an=1G (dove n è la cardinalità di G), il periodo k=ord(a) di un qualunque elemento di G è sempre divisore della cardinalità n del gruppo.
Si ha poi che due potenze as, at (con esponenti s,t0) coincidono se e solo se st (mod k=ord(a)):
infatti, se per esempio st, l’eguaglianza as=at è equivalente all’eguaglianza as-t=1G, e come già visto ciò avviene se e solo se k(s-t).
Riassumendo:
Se G è un gruppo commutativo finito di cardinalità n, per ogni aG si può definire il periodo dell’elemento a come il minimo numero naturale k=ord(a) tale che ak=1G : tale numero è divisore di n. Le potenze di base a ed esponente 0 sono tutte e sole quelle con esponente 0,1,…,k-1 e sono distinte (quindi sono in numero di k); si ha inoltre ah=1G ord(a)= kh , e anche as=at st (mod k).
Teorema di Eulero-Fermat.
Siano a,n due naturali coprimi (con n>1). Allora a(n)1 (mod n).
Dimostrazione:
Il gruppo commutativo finito G= Zn* ha cardinalità (n), ed essendo a,n coprimi, si ha [a]G.
Per un risultato dimostrato in precedenza, ogni elemento di un gruppo finito commutativo elevato alla cardinalità del gruppo dà come risultato l’elemento neutro: nel nostro caso si ha [1]=[a](n)=[a][a]….[a]=[aa….a]=[a(n)]
da cui la tesi.
Corollario (Piccolo Teorema di Fermat).
Se n è un numero primo, per ogni naturale a non multiplo di n si ha an-11 (mod n).
Dimostrazione:
Essendo a non multiplo del primo n, i numeri a,n sono coprimi (perché le uniche possibilità per il mcd(a,n) sono 1, n). Poiché (n)=n-1 (perché n è primo) la tesi segue dal Teorema di Eulero- Fermat.
Test di primalità.
Ricordiamo che un test di primalità deterministico è un algoritmo tale che, dato in input un numero naturale n>1, produce un output “n è primo” oppure “n è composto” (definendo composto un naturale >1 non primo), e tale che l’output sia “n è primo” se e solo se l’input n è un numero primo.
Oltre il test ingenuo di primalità (che verifica, per d=2,….,n-1, se esiste un d divisore non banale di n) un altro test di primalità deterministico segue dal seguente risultato:
Teorema di Wilson.
Sia n> 1 un numero naturale . Allora: n è primo (n-1)!-1 (mod n).
Dimostrazione:
(): Consideriamo il gruppo moltiplicativo Zn* . Se n è primo, n è coprimo con tutti i numeri 1,2,
…,n-1 (perché non sono multipli di n, essendo <n), dunque Zn* = {[1], [2], ….., [n-1]}.
Calcoliamo il prodotto di tutti gli elementi di tale gruppo:
[1][2] …..[n-1] = [12 …..(n-1)] = [(n-1)!].
In tale prodotto, sfruttando la proprietà commutativa, possiamo accoppiare ogni elemento [i] con il suo inverso [i]-1 (nel caso in cui [i][i]-1) ottenendo per ogni tale coppia il prodotto =[1]: al termine di tale semplificazione il prodotto precedente si riduce a quello dei soli fattori [i] tali che [i]=[i]-1, cioè tali che [i]2=[i2]=[1].
Ma per un tale i si ha n(i2-1), n(i+1)(i-1), quindi (essendo n primo) n(i+1) oppure n(i-1), ossia i1 (mod n) oppure i -1 (mod n). Si conclude che:
[(n-1)!]=[1][-1]=[-1] , da cui la tesi.
(): Sia (n-1)!+1=kn, con k intero. Se per assurdo esistesse un divisore non banale d di n, con 1<d<n, tale d sarebbe divisore di 1=kn-(n-1)! (perché d è uno dei fattori del prodotto (n-1)!) contraddizione perché d>1.
Nota: la condizione (n-1)!-1 (mod n) del Teorema di Wilson equivale ovviamente alla condizione (n-1)!modn=(n-1)
(in quanto -1(n-1) (mod n)).
Il Teorema di Wilson permette di costruire il seguente test di primalità deterministico:
1) in input il naturale n>1
2) si costruisce la la successione y1,y2,…,yn-1 ponendo y1=1, e per i>1 yi=(iyi-1)modn: notare che per ogni i>1 si ha yi i! (mod n), come si dimostra facilmente per induzione (Ia forma), e dunque per i=n-1 si ha yn-1(n-1)! (mod n), ossia yn-1=(n-1)!modn (in quanto 0 yi n-1)
3) se yn-1=(n-1) si esce con output “n è primo”; altrimenti si esce con output “n è composto”.
Esaminando la complessità di tale algoritmo, si verifica che, nonostante la costruzione di ogni termine yi si possa effettuare con algoritmi “efficienti” di complessità polinomiale, il numero dei termini yi da calcolare è di ordine O(n) lineare rispetto all’input n, quindi di ordine esponenziale O(2x) rispetto ad x=L(n).
Quindi tale algoritmo di primalità non è affatto “efficiente”.
Ricordiamo che un test di primalità probabilistico è un algoritmo tale che, dato in input un numero naturale n>1, dopo una serie di calcoli che coinvolgono anche alcuni elementi casuali, produce un output “n è primo” oppure “n è composto”, con la condizione che se l’input n è un numero primo allora l’output è sempre “n è primo” (si dice anche che “tutti i numeri primi superano il test”), ma se n è composto, l’output può essere sia “n è primo” sia “n è composto”, e la probabilità che l’output sia “n è primo” (pur essendo l’input n composto) è maggiorata da una costante C<1, indipendente dall’input n e dagli elementi casuali.
Se un input n>1 supera un test di primalità probabilistico un numero k di volte (con gli elementi casuali scelti ogni volta in modo indipendente), la probabilità che il numero n sia composto si può dunque rendere piccola a piacere (essa è maggiorata da Ck, che è un numero piccolo a piacere se il numero di test k è abbastanza grande), quindi si può accettare che n sia effettivamente primo, con una bassa percentuale di errore.
Esamineremo alcuni test di primalità probabilistici, di complessità polinomiale, quindi efficienti.
Il primo è il cosiddetto test di Fermat (basato sul Piccolo Teorema di Fermat): in realtà esso non è un test probabilistico a tutti gli effetti, perché vedremo che la probabilità che un numero composto superi (erroneamente) il test è maggiorata dalla costante C=1/2 (indipendente dall’input e dagli elementi casuali), ma ciò non avviene per tutti gli input composti.
Dunque tale test si può definire test probabilistico ma con delle “eccezioni” . I passi dell’algoritmo sono:
1) in input il numero naturale n>1
2) si sceglie casualmente un intero a con 1 a n-1 (detto base) 3) si calcola d=mcd(a,n); se d>1 si esce con output ”n è composto”
4) se d=1 si calcola la riduzione y=an-1modn : se y1 si esce con output ”n è composto”; altrimenti si esce con output “n è primo”
Osserviamo prima di tutto che ogni input n primo supera il test: se 1 a n-1, certamente a non è multiplo di n e quindi nel passo 3) si ha d=1; per il Piccolo Teorema di Fermat si ha allora (nel passo 4)), y=1 e quindi si esce con output “n è primo”.
Dunque se un input n non supera il test di Fermat possiamo affermare con certezza che n non è un numero primo.
