Numerele au avut o istorie fascinant a de-a lungul ultimilor trei mii de ani. Numerele 1, 2, 3, 4, 5, . . . se numesc cardinale  si arat a din c^… [601307]

1 Numere prime
1.1 Cu  si despre numere
Numerele au avut o istorie fascinant a de-a lungul ultimilor trei mii de ani. Numerele 1, 2,
3, 4, 5, . . . se numesc cardinale  si arat a din c^ ate unit at i se compune ecare. Num arul este
cea mai simpl a not iune abstract a deoarece este exprimat prin anumite semne convent ionale.
S irul numerelor naturale s-a format pornind de la o unitate  si ad aug^ and pe r^ and c^ ate o
unitate num arului precedent. Euclid denea num arul ca ind o mult ime \compus a din
unit at i", iar \unitatea este aceea potrivit c areia ecare lucru se nume ste unu".
Denit ie 1.1 Un num ar natural p>1se nume ste prim dac a se divide doar cu 1  si cu
el ^ nsu si.
Acum 2300 de ani, Euclid a justicat c a mult imea numerelor prime este innit a, oferind
urm atoarea demonstrat ie.
Teorem a 1.1 (Euclid) Mult imea numerelor prime este innit a.
Demonstrat ie: Presupunem prin reducere la absurd c a num arul de numere prime este nit  si
not amP=fp1; p2; :::; pngmult imea tuturor numerelor prime. Construim acum num arul
pn+1=p1p2:::pn+ 1. Evident c a num arul pn+1nu se divide cu niciunul dintre elementele
mult imiiP. Asta ^ nseamn a c a num arul pn+1este num ar prim  si nu face parte din mult imea
P. Putem introduce num arul pn+1^ n mult imeaP si apoi s a repet am procedeul. ^In concluzie
presupunerea f acut a este fals a, deci mult imea numerelor prime este innit a. 
O problem a care a dus la dezvoltarea teoriei numerelor  si care este ^ nc a nerezolvat a, ^ n
ciuda faptului c a cei mai str alucit i matematicieni au ^ ncercat s a o rezolve ^ n ultimii 250 de
ani, este ipoteza lui Goldbach.
Figure 1: Christian Goldbach
Problema a fost trimis a pe data de 7 iunie 1742 de Christian Goldbach lui Leonard
Euler, ambii matematicieni la Academia din Sankt Petersburg. Goldbach ^ i scria lui Euler:
\Evident, orice num ar(natural) este suma a trei numere prime". ^In acea perioad a 1 era
considerat num ar prim. Euler ^ i r aspunde : \Consider ca o teorem a pe deplin adevarat a c a
orice num ar par este suma a dou a numere prime, de si nu pot s a o demonstrez" .
1

P^ an a ^ n anul 1970, numerele prime erau considerate utile doar ^ n matematica teoretic a,
neind folosite ^ n practic a. ^In anul 1977 a fost realizat a prima schem a criptograc a cu
chei publice de c atre Ron Rivest, Adi Shamir  si Len Adleman. Schema criptograc a se
bazeaz a pe dicultatea factoriz arii numerelor ^ ntregi, iar generarea cheilor se face folosind
dou a numere prime foarte mari.
1.2 Not iuni de teoria numerelor
1.2.1 Divizibilitate
Denit ie 1.2 Se nume ste triplet Peano un triplet (N;0;s)undeNeste o mult ime
nevid a, 02N , iars:N!N este o funct ie care veric a urm atoarele axiome:
A1: 0=2s(N)(0nu este succesorul nici unui num ar natural).
A2:seste o funct ie injectiv a.
A3:presupunem c aPeste o submult ime a lui Nastfel ^ nc^ at 02P  si(n2P)s(n)2P),
atunciP=N.
Fie tripletul Peano ( N;0;s) xat. Elementele lui Nse numesc numere naturale. Not am
N=Nnf0g;1 =s(0);2 =s(1);3 =s(2); ::: astfel avem c a N=f0;1;2;3;:::g.
Funct iaspoart a numele de funct ia succesor, axiomele A1A3sunt cunosute ca axiomele
lui Peano, iar A3se nume ste axioma induct iei matematice.
Denit ie 1.3 O relat ie binar a pe o mult ime Aeste o submult ime a produsului cartezian
AA .
Denit ie 1.4 O relat ie binar aAA pe o mult imeAse nume ste relat ie de ordine
dac a ^ ndepline ste urm atoarele propriet at i:
re
exivitate:8x2A;xx
antisimetrie:8x; y2A, dacaxy siyxatuncix=y
tranzitivitate:8x; y; z2A dac axy siyzatuncixz
Tipuri speciale de relat ii de ordine :
Ordine total a
O relat ie de ordine ^ n care orice dou a elemente sunt compatibile, adic a 8x;y2A; xy
sauyxse nume ste relat ie de ordine total a.
Bun a ordonare
O relat ie de ordine total a ^ n care ^ n plus orice submult ime nevid a admite un minim
se nume ste relat ie de bun a ordonare, iar mult imea pe care s-a stabilit relat ia se nume ste
mult ime bine ordonat a.
Denit ie 1.5 Fiea;b2N. Spunem c a aeste mai mic sau egal dec^ at bsau c abeste
mai mare sau egal dec^ at adac a exist a k2Nastfel ^ nc^ at a+k=b si not amab. Dac a
k2N, atunci avem a6=b siab, ^ n cazul acesta spunem c a aeste strict mai mic dec^ at
b si not ama<b .
2

Propozit ie 1.1 Dubletul (N;)este o mult ime total ordonat a.
Demonstrat ie:
1
Ar at am c aeste o relat ie de ordine pe N. Deoarece pentru orice n2N,n+ 0 =n
deducem c a nn, prin urmare relat ia este re
exiv a.
Fiem; n2Na.^ .mn sinm. Conform denit iei 1.5 exist a p; q2Na.^ .m+p=n si
n+q=m. Avemm+p+q=m, de undep+q= 0 adic ap=q= 0 decim=n si relat ia
este antisimetric a.
Fiem; n; p2Na.^ .mn sinp. Atunci conform denit iei 1.5 exist a r; s2Na.^ .
m+r=n sin+s=p. Observ am c a m+ (r+s) =p, adic amp, deci relat iaeste
tranzitiv a. Deoarece relat ia este re
exiv a, antisimetric a  si tranzitiv a rezult a c a este o
relat ie de ordine pe N.
2
Ar at am c a relat ia este total a. Fie m2Nxat. Consider am Qm=fn2N:n
m sau mngN. Evident 02Qm si en2Qm. Dac an=m, atunci cum n < s (n)
avemm<s (n), adic as(n)2Qm. Dac an<m , atunci avem s(n)m sis(n)2Qm. Dac a
m < n , cumn < s (n) avemm < s (n)  sis(n)2Qm. Deducem c aQm=N si cummeste
oarecare deducem c a relat ia de ordine de peNeste total a . 
Teorem a 1.2 Dubletul (N;)este o mult ime bine ordonat a.
Demonstrat ie: Ar at am c a orice submult ime nevid a BNare un cel mai mic element.
Consider amQ=fn2N:nx pentru orice x 2Bg N, evident 02Q. Dac a pentru
oricen2Q ar rezultas(n)2Q, atunci am deduce c a Q=N. Astfel c a aleg^ and un x02B
atuncix02Q, decis(x0)2Q  si ar rezulta s(x0)x0contradict ie. Deci Q6=N si exist a
a2Qa.^ .s(a)=2Q. Ar at am c a a2B si c aaeste cel mai mic element al lui B. Dac aa =2B,
atunci pentru orice x2Bavema<x , de undes(a)x, adic as(a)2Q contradict ie, deci
a2B  si cuma2Q deducem c a axpentru orice x2B, rezult a c a aeste cel mai mic
element al luiB. 
Denit ie 1.6 Fiem sindou a numere naturale, spunem c a mdividen si scriemmjn
dac a exist a un num ar natural kastfel ^ ncat n=km.^In acest a situat ie, mse nume ste
divizor al lui n. Este evident c a orice num ar n > 1are cel put in doi divizori: pe 1  si pe
el ^ nsu si. Prin divizor propriu al lui n^ nt elegem un divizor diferit de num arul n, iar prin
divizor netrivial al lui n, un divizor diferit de 1  si n.
Relat iajdenit a pe Nse nume ste relat ie de divizibilitate pe N, se poate ar ata c a este o
relat ie de ordine pe N.
Teorem a 1.3 (Teorema ^ mp art irii cu rest) Fie m sindou a numere naturale cu
condit ia ca ns a e nenul, atunci exist a  si sunt unice numerele naturale q; r astfel ^ nc^ at
m=nq+r sir<n .
Demonstrat ie:
Fie mult imeaA=fs2Nj9k2N;m=nk+sg.
3

Dinm=n
0 + 0 avem c a m2A, deci mult imeaAnu este vid a. Atunci, conform teoremei
1.2Neste bine ordonat a, prin urmare exist a rcel mai mic element din A. Putem presupune
c a exist aq2Nastfel ^ nc^ at m=n
q+r si ar at am c a r <n . Dac a presupunem c a rn,
atuncir=n+u, pentru un n2N sim=nq+r=nq+n+u=n(q+ 1) +u, astfelu2A,
darru, obt inemr=u, de unden= 0, fals. Deci r <n  si am demonstrat c a exist a q si
r2Na.^ .m=nq+r. Ar at am c a q sirsunt unice. Presupunem c a
m=nq+r
m=np+s r;s<n .
Dac aq <p , atuncip=q+u,u6= 0. Obt inem c a nq+r=n(q+u) +s=nq+ (nu+s),
adic ar=nu+sn+uncontradict ie c aci r <n . Deducem c a p=qde unde rezult a
c ar=s. 
Denit ie 1.7 Fie numerele ^ ntregi m sin. Spunem c a mdividen si scriemmjndac a
exist a un ^ ntreg kastfel ^ nc^ at n=km. Relat iajdenit a pe Zse nume ste relat ie de di-
vizibilitate pe Z. Se poate ar ata c a aceast a relat ie este re
exiv a  si tranzitiv a, dar nu este
antisimetric a. Pentru a obt ine o relat ie de echivalent  a pe Zse introduce o relat ie de asociere
^ n divizibilitate:
xy,x=y
Teorem a 1.4 (Teorema ^ mp art irii cu rest) Fie a; b2Zcub6= 0. Atunci, exist a  si
sunt uniceq; r2Za.^ .a=bq+runde 0r<jbj.
Demonstrat ie:
Dac aa= 0 atunci a=b
0 + 0, 0<jbj si lu amq=r= 0.
Cazul 1: Dac a a>0  sib>0 aplic am teorema 1.3.
Cazul 2: Dac a a<0  sib<0, aplic am aceea si teorem a 1.3 pentru numerele naturale a
 sib. Rezult a astfela=bq0+r0, 0r0<b. Dac ar0= 0, alegem q=q0 sir= 0.
Dac ar0>0, avema=bq0r0=b(q0+ 1) + (br0). Lu amq=q0+ 1; r=br0. Cum
0<r0<b, rezult a 0<r<b=jbj.
Cazul 3: Dac a a < 0  sib > 0 aplic am teorema 1.3 pentru a sib. Rezult a astfel
a=bq0+r0, 0r0< b. Dac ar0= 0, atunci a=bq0 si alegemq=q0,r= 0. Pentru
cazul 0< r0, avema=bq0r0=b(q01) + (br0). Alegemq=q01;r=br0.
Cum 0<r0<b, obt inem 0 <r<b =jbj.
Cazul 4: Dac a a > 0  sib < 0 aplic am teorema 1.3 pentru a sib. Rezult a astfel
a= (b)q0+r0undeq0,r02N si 0r0<b=jbj. Lu^ andq=q0 sir=r0, rezult a
a=bq+rcu 0r<b=jbj.
Ar at am c a q sirsunt unice. Presupunem c a a=bq+r sia=bq0+r0cu 0r; r0<jbj.
Rezult ab(qq0) =r0r, decijbj
jqq0j=jrr0j. Cumr sir0sunt numere naturale cu
0r; r0<jbj, avemjrr0j<jbj. Astfel,jbj
jqq0j<jbj, de undejqq0j<1. Atunci,q=q0
 sir=r0. 
4

1.2.2 Congruent e
Denit ie 1.8 Fiemnum ar natural  si a,bdou a numere ^ ntregi. Spunem c a ab
(modm)dac amdivideab.
Teorem a 1.5 Fiemun num ar natural  si a; b; c ^ ntregi atunci :
1. Dac aab(modm), atunciba(modm).
2. Dac aab(modm)  sibc(modm), atunciac(modm).
3. Dac aab(modm), atuncia+cb+c(modm).
4. Dac aab(modm), atunciacbc(modm).
5. Dac aab(modm), atunciacbc(modm).
6. Dac aab(modm), atunciacbc(modmc), pentruc>0.
7. Dac aab(modm)  sicd(modm) atuncia+c(b+d) (modm).
8. Dac aab(modm)  sicd(modm) atunciac(bd) (modm).
9.Dac aab(modm)  sicd(modm) atunciacbd(modm).
Demonstrat ie:
1. S tim c a ab(modm), atuncimj(ab). Dinmj(ab) rezult a c a exizt a k2Za.^ .
ab=mk, de undeba=m(k). Decimjba si avem c a ba(modm).
2. S tim c a ab(modm), atuncimj(ab)  si dinbc(modm) avemmj(bc). Deci
exist ak; l2Za.^ .a=b+mk sib=c+ml, de undea=c+m(k+l) deciac(modm).
3. S tim c a ab(modm), atuncimj(ab)  si dac a adun am si sc adem un cobt inem
nj((a+c)(b+c) de undea+cb+c(modm).
4. S tim c a ab(modm), atuncimj(ab)  si dac a sc adem  si adun am un cobt inem
nj((ac)(bc) de undeacbc(modm).
5. S tim c a ab(modm), atuncimj(ab), deci exist a k2Za.^ .ab=mk si
acbc=m(kc). Avem c a mj(acbc), deciacbc(modm).
6. S tim c a ab(modm), atuncimj(ab), deci exist a k2Za.^ .ab=mk, de unde
acbc=mc(k). Decimcjacbc,acbc(modmc).
7. S tim c aab(modm), atuncimj(ab)  si dincd(modm) avem c amj(cd). Deci
exist ak; l2Za.^ .ab=mk,  sicd=ml. Cum (ab)+(cd) = (a+c)(b+d) =m(k+l),
avemmj((a+c)(b+d) de undea+cb+d(modm).
8. Dac aa=b+mk sic=d+mlatunci (ab)(cd) = (ac)(bd) =m(kl)  si
mj((ac)(bd) deciacbd(modm).
9. Exist ak; l2Za.^ .ab=mk sicd=ml si ^ nmult ind prima egalitate cu c si pe
a doua cubobt inemcacb=m(ck)  sibcbd=m(bl) de unde ( cacb) + (bcbd) =
acbd=m(kcbl) decimj(acbd) adic aacbd(modm). 
Denit ie 1.9 Se nume ste sistem complet de resturi (scr) modulo no mult ime de numere
^ ntregi astfel ^ nc^ at orice ^ ntreg este congruent modulo ncu un singur num ar din mult ime.
Denit ie 1.10 Se nume ste congruent a liniar a ^ ntr-o variabil a o ecuat ie de forma axb
(modm)undex2Zeste necunoscuta.
5

Observat ie 1.1 Dac axeste o solut ie a congruent ei axb(modm), iarxx1
(modm), atunciaxax1(modm)adic aax1b(modm)de aici avem c a  si x1este
solut ie a congruent ei axb(modm).
Teorem a 1.6 (Teorema chinezeasc a a resturilor) Fie rnumere naturale m1; m 2; :::; m r
astfel ^ nc^ at oricare ar  i6=javem (mi;mj) = 1 . Atunci sistemul
(S)8
>>>><
>>>>:xa1(modm1)
xa2(modm2)
:::::::::::::::::::::::::::
xar(modmr)
are solut ie unic a modulo M=m1m2:::mr.
Demonstrat ie: Pentru orice k2f1;2; :::;rgconsider am Mk=M
mk. Din ipotez a avem
c a (mj;mk) = 1 pentru orice j6=k. Obt inem astfel c a ( Mk;mk) = 1. Fie Mkun invers al
luiMkmodulomk, prin urmare MkMk1 (modmk). Not amx=Pr
t=1atMtMt si ar at am
c axeste solut ie pentru sistem. Fie k2f1;2; :::;rg,kxat . Atunci, mkjMjpentru orice
j6=k. Astfel,Mj0 (modmk) pentruj6=k. Obt inem xakMkMkak(modmk).
Ar at am c a xeste unica solut ie modulo M. Presupunem prin reducere la absurd c a x0 six1
sunt dou a solut ii ale sistemului ( S). Atunci, x0x1(modmk) pentru 1kr. Deci
rezult a c ax0x1(modM), deci orice dou a solut ii ale sistemului sunt congruente modulo
M. 
Propozit ie 1.2 Fiepun num ar prim  si a2Zprim cup. Atunci,aeste propriul s au
invers modulo pdac a si numai dac a a1 (modp).
Demonstrat ie: aa=a21 (modp) este echivalent cu pja21 adic apja1 saupja+ 1.
Deci,a1 (modp). 
Teorem a 1.7 (Teorema lui Wilson) Num arul natural p>1este prim dac a  si numai
dac a (p1)!1 (modp).
Demonstrat ie:
)Presupunem c a peste num ar prim. Dac a p= 2 atunci ( p1)! = 11 (mod 2).
Dac ap= 3 atunci ( p1)! = 21 (mod 3). Presupunem deci p > 3. Orice element
a2 f^2;^3; :::; ^p2geste inversabil  si a6=a12 f^2;^3;:::; ^p2g. Rezult a deci c a
grup^ and cele p3 elemente din mult imea de mai sus ^ n perechi ( a; a1), produsul lor este
^12Zp. Deci 2
3:::(p3)(p2)1 (modp)  si (p1)! = 1
(p1)1 (modp).
(Presupunem acum c a ( p1)!1 (modp)  si vom demonstra c a peste num ar prim.
Vom folosi metoda reducerii la absurd. Presupunem c a pnu este prim, deci exist a un
num ar natural da.^ .djp si 1<d<p . Atuncidj(p1)!  sidj(p1)! +1 de unde dj1 adic a
d= 1contradic t ie. Presupunerea f acut a este fals a deci peste prim. 
6

Teorem a 1.8 (Mica teorem a a lui Fermat) Dac a peste un num ar prim  si nun num ar
natural astfel ^ nc^ at (n;p) = 1 , atunci avem pjnp11 (np11 (modp)).
Demonstrat ie: Consider am primii p1 multipli ai num arului n: 1
n;2
n;3
n; :::; (p
1)
n. Resturile ^ mp art irii acestora la psunt respectiv: r1; r2; :::; rp1. A sadar, avem
relat iile:
i
n=p
ci+ri, 0ri<p(i= 1;2;3; :::; p1)(1).
Observ am c a ri6= 0 pentru orice i= 1;2;3; :::; p1; ^ n caz contrar, ar urma c a pji
n,
decipjn, ceea ce contrazice ipoteza ( n;p) = 1. Mai observ am c a resturile r1; r2; :::; rp1
sunt diferite ^ ntre ele; dac a am avea ri=rj, atunci ar rezulta ( ij)
n=p
(cicj), de
undepjn, din nou ^ n contradict ie cu ipoteza. Aceste armat ii permit s a concluzion am c a
r1; r2; :::; rp1sunt numerele 1 ;2;3; :::; rp1aranjate ^ ntr-o anumit a ordine. ^Inmult ind
egalit at ile (1), vom obt ine
1
2
:::
(p1)
np1= (pc1+r1)
(pc2+r2)
:::
(pcp1+rp1)
sau 1
2
:::
(p1)
np1=p
t+r1r2r3:::rp1,t2N,
deci 1
2
:::
(p1)
np1=p
t+ 1
2
:::
(p1),
adic a 1
2
:::
(p1)
(np11) =pt,t2N,
de undepjnp11 . 
Denit ie 1.11 Funct ia:N!N, denit a prin (n)este num arul numerelor naturale
mai mici dec^ at n si prime cu n, poart a numele de funct ia lui Euler.
Observat ie 1.2
1. Dac an=p; pprim atunci (p) =p1.
2. Dac an=p1k1


prkr,p1;:::;prprime atunci (n) = (p11)pk11
1:::(pr1)pkr1
r.
Denit ie 1.12 Un sistem redus de resturi modulo neste o mult ime de (n)numere
^ ntregi, toate prime cu n si dou a c^ ate dou a necongruente modulo n.
Propozit ie 1.3 Fie(n) =k sifa1; a2; :::; akgun sistem redus de resturi modulo n
a.^ .(m;n) = 1 , atunci  sifma1; ma 2; :::; ma kgeste un sistem redus de resturi modulo n.
Demonstrat ie: Dac a (m;n) = 1, putem g asi xa.^ .mx1 (modn), cum (ai;n) = 1,
putem g asi bia.^ .aibi1 (modn) , apoi (xbi)(ami) = (mx)(aibi)1 (modn) de unde
avem c aamieste inversabil mod n, prin urmare ( ami;n) = 1.
Dac amai=maj(modn ), atuncixmai=xmaj(modn ) adic aai=aj(modn )contradic t ie(ai6=
aj). Prin urmarefma1;ma 2;:::;ma kgeste un sistem redus de resturi modulo n. 
Teorem a 1.9 ( Teorema lui Euler) Fie a2Z,n2Ncu(a;n) = 1 . Atunci,a(n)1
(modn).
Demonstrat ie:
Fiefr1; r2; :::; r(n)gun sistem redus de resturi modulo n. Conform propozit iei anterioare,
far1; ar 2; :::; ar (n)geste un sistem redus de resturi modulo n. Deci, resturile modulo n
ale numerelor ar1; ar 2; :::; ar (n)suntr1; r2; :::; r(n), eventual ^ n alt a ordine. Atunci,
a(n)r1r2:::r(n)r1r2:::r(n)(modn), deci obt inem a(n)1 (modn). 
7

1.3 Numere prime speciale
Prin numere prime speciale ^ nt elegem numere prime care au o anumit a form a. De exemplu
numerele Mersenne Mqsau numerele Fermat Fndenite prin:
Mq= 2q1
Fn= 22n+ 1;n0
sunt uneori prime.
1.3.1 Numere Fermat
^In 1637 Fermat sust ine c a toate numerele Fn= 22n+ 1 ,n0 sunt prime,  si ^ ntr-adev ar
primele cinci, p^ an a la F4= 65537 inclusiv sunt prime. Cu toate acestea Fermat a gre sit c aci
F5nu mai este prim, aceasta este una dintre put inele situat ii ^ n care Fermat gre se ste. ^In
1732 Euler a ar atat c a F5nu este prim. Demonstrat ia se bazeaz a pe relat ia :
641 = 5
27+ 1 = 24+ 54
F5= 225+ 1 = 232+ 1 = 24
228+ 1
= (64154)
228+ 1 = 641
22854
228+ 1
= 641
228(5
27)4+ 1
= 641
228(6411)4+ 1
(6411)4= (6411)2
(6411)2
= (64122
641 + 1)(64122
641 + 1)
= 64142
6413+ 64122
6413+ 4
64122
641 + 64122
641 + 1
F5= 641
2286414+ 4
64136
6412+ 4
6411 + 1
F5= 641
(2286413+ 4
64126
641 + 4)
F5= 225+ 1 = 641
6700417 = 4294967297 :
Lem a 1.1 Pentru orice n2N; n2 si pentru orice a; b2Ravem :
anbn= (ab)n1X
k=0an1k
bk:
Demonstrat ie: Fie
P(n) :anbn= (ab)n1X
k=0an1k
bk;n2; a; b2R
I.
P(2) :a2b2= (ab)
1X
k=0a21kbk
a2b2= (ab)(a+b)
8

II.
P(n))P(n+ 1)
P(n) :anbn= (ab)n1X
k=0an1k
bk;n2;a;b2R
P(n+ 1) :an+1bn+1= (ab)nX
k=0ank
bk;n2;a;b2R
(ab)nX
k=0ank
bk= (ab)
(n1X
k=0ank
bk+ann
bn) =
= (ab)(n1X
k=0a
an1k
bk+bn) =a
(ab)
n1X
k=0an1k
bk+ (ab)
bn=
=a
(anbn) + (ab)
bn=an+1a
bn+a
bnbn+1=an+1bn+1:
Teorem a 1.10 Dac a 2k+ 1este prim, atunci keste o putere a lui 2.
Demonstrat ie: Presupunem c a knu este o putere a lui 2 deci exist a s>2; simpar
a.^ .k=r
s, 1r<k . Din lema anterioar a avem c a ( ab)j(ambm).^Inlocuinda= 2r,
b=1,m=s si folosind c a s-impar avem c a 2r+ 1j2rs+ 1 adic a 2r+ 1j2k+ 1 deci 2k+ 1
nu e primcontradic t ie.
Presupunerea f acut a este fals a deci ktrebuie s a e o putere a lui 2. 
Propozit ie 1.4 Pentrun1,
Fn= (Fn11)2+ 1:
Demonstrat ie:
Fn= (Fn11)2+ 1 = (22n1+ 11)2+ 1 = 22n+ 1 =Fn:
Propozit ie 1.5 Pentrun1,
Fn=F0:::Fn1+ 2:
Demonstrat ie:
Fie
P(n) :Fn=F0:::Fn1+ 2;n1
I.
P(1) :F0+ 2 = 3 + 2 = F1
II.
P(n))P(n+ 1)
9

Fn=F0:::Fn1+ 2
Fn+1=F0:::Fn+ 2
F0:::Fn+ 2 =F0:::Fn1
Fn+ 2 =
= (Fn2)
Fn+ 2 = (22n1)(22n+ 1) + 2 = 22n+ 1 =Fn+1
Deoarece
Fn2 =F0:::Fn1
avem c a:
FkjFn2;8k2f0; :::; n1g
DeciFn2 (modFk). 
Propozit ie 1.6 Pentrun2
Fn=F2
n12
(Fn21)2:
Demonstrat ie:
F2
n12
(Fn21)2= (22n+1)22
(22n1+1)2= 22n+2
22n1+12
22n1= 22n+1 =Fn:
Propozit ie 1.7 Pentrun2
Fn=Fn1+ 22n1
F0
:::
Fn2:
Demonstrat ie:
Fie
P(n) :Fn=Fn1+ 22n1
F0
:::
Fn2
I.
P(2) :F1+ 22
F0= 5 + 22
3 = 17 =F2
II.
P(n))P(n+ 1)
P(n) :Fn=Fn1+ 22n1
F0
:::
Fn2
P(n+ 1) :Fn+1=Fn+ 22n
F0
:::
Fn1
Fn+ 22n
F0
:::
Fn1=Fn+ 22n1(22n1
F0Fn2)Fn1=Fn+ 22n1
Fn1(FnFn1) =
= 22n+ 1 + 22n1(22n1+ 1)(22n22n1) = 22n+ 1 + 22n1(22n1+ 1)
22n1
(22n11) =
= 22n+ 1 + 22n(22n1) = 22n+ 1 + 22n+122n= 22n+1+ 1 =Fn+1: 
1.3.2 Numere Mersenne
Denit ie 1.13 NumereleMn= 2n1; n1se numesc numere Mersenne.
10

Teorem a 1.11 Dac a 2p1este prim, atunci peste prim.
Demonstrat ie:
Presupunem c a pnu este prim, ci compus, deci exist a a sib>1 a.^ .p=a
b.
Deci 2p1 = 2ab1 = (2a)b1 = (2a1)[(2a)b1+ (2a)b2+


+ 1]contradict ie c aci
2p1 este prim. Am folosit c a: xn1 = (x1)(xn1+xn2+


+ 1). 
Teorem a 1.12 Dac aa; b2Na.^ .ap1este prim, atunci a= 2 saup= 1.
Demonstrat ie:
a1 (moda1)
ap1 (moda1)
ap10 (moda1)
a1jap1
Darap1 este prim. Deci 1
a1 =ap1 sau 2
a1 =1:
1
Dac aa1 =ap1atunci a =ap:Dac ap > 1 atuncia2f0;1g(contradict ie c aci
0p1 =1, (1)p1 = 0 pentru p-par  siap1 prim ), deci p= 1.
2
Dac aa= 0 atunci 0p1 =1 care nu e prim, prin urmare a= 2. 
Denit ie 1.14 Un num arn2Neste perfect dac a este egal cu suma divizorilor(pozitivi)
<n.
Denit ie 1.15 Fie
:N!N
(n) =X
djnd8n2N:
Observat ie 1.3 neste perfect,(n) = 2
n.
Denit ie 1.16 Fieho funct ie aritmetic a (domeniul este mult imea numerelor naturale).
Dac a avem relat ia h(x1
x2) =h(x1)
h(x2);8×1; x22N si gcd(x1; x2)=1 atunci hse
nume ste funct ie multiplicativ a. Dac a h(x1
x2) =h(x1)
h(x2);8×1; x22Natuncihse
nume ste complet multiplicativ a.
Propriet at i
1.(n) = 1
2. dac ape prim atunci (p) =p+ 1
3. dac ape prim atunci (pj) = 1 +p+


+pj=pj+11
p1
4. dac a (n1; n2) = 1 atunci (n1)
(n2) =(n1
n2):
Teorem a 1.13 (Euler-Euclid) Fie n2N,npar. Atunci ne perfect,n= 2p1
Mp,
Mpprime.
11

Demonstrat ie:
(Notezq=Mp,  stim c an= 2p1
q. Ar at am c a neste perfect i.e. (n) = 2n. Deoarece
(2p1; q) = 1 avem c a (n) =(2p1
q) =(2p1)
(q) = (2p1)
(q+1) = 2p
q+2pq1 =
2p
q+ 2p2p+ 11 = 2p
q= 2p
(2p1) = 2
2p1
(2p1) = 2n:
)Fiennatural, par.
Deoarecene par putem scrie c a n= 2j
m,j1,mimpar6=n.
(n) =(2j)
(m) = (2j+11)
(m) . Darnperfect)(n) = 2n= 2j+1
m.
Deci 2j+1
m= (2j+11)
(m), dar 2j+11 impar, de unde rezult a c a 2j+1j(m) adic a
exist ar1 a.^ .(m) =r
2j+1, 2j+1
m= (2j+11)
r
2j+1, de undem= (2j+11)
r.
Presupunem c a r >1, deoarece m= (2j+11)
ratunci 1,r simsunt 3 divizori distinct i
(din ipotez a r6= 1, dac ar=matuncij= 0  sin=mcontradict ie c aci mimpar). Prin
urmare(m)1 +r+m= 1 +r+ (2j+11)
r= 1 + 2j+1
r= 1 +(m)contradict ie.
Decir= 1 de unde (m) = 2j+1; m= 2j+11,n= 2j
m= 2j
(2j+11) = 2j
Mj+1.
Ar at c aMj+1este prim adic a (m) =m+ 1, dar 2j+1=(m) = 2j+11 + 1, deci meste
prim. 
1.3.3 Pseudoprime cu baza a
Denit ie 1.17 Un num ar compus ne pseudoprim cu baza adac aana(modn).
Denit ie 1.18 Un num ar Carmichael este un num ar compus na.^ .ana(modn)
pentru orice a2Z.
Denit ie 1.19 Fiea6= 0; n> 0relativ prime. Ordinul lui amdulonestex=ordn(a)
doar dac axeste cel mai mic num ar pentru care ax1 (modn).
Denit ie 1.20 Fier sinrelativ prime, r6= 0; n > 0. Atuncirse nume ste r ad acin a
primitiv a modulo ndac a ord n(r) =(n).
Propozit ie 1.8 Orice num ar Carmichael neste impar.
Demonstrat ie: Fienun num ar Carmichael. Presupunem prin reducere la absurd c a neste
par. Deoarece nveric aana(modn),a2Z, considera=1:Avem c a (1)n= 11
(modn), pe de alt a parte 1n1 (modn), decin11 (modn) de unde avem c a
n2 (modn), pentrun= 2 obt inem contradict ie(deoarece 2 e prim). 
Teorem a 1.14 (Criteriul lui Korselt) Fie n >1compus. Urm atoarele armat ii sunt
echivalente:
1.ana(modn)pentru orice a2Z
2.an11 (modn)pentru orice a2Zrelativ prim cu n
3.neste impar, liber de p atrate  si p1jn1pentru orice divizor prim pal luin.
Demonstrat ie:
1.)2. S tim c a ana(modn)  si presupunem c a ( a; n) = 1. Deoarece ( a; n) = 1 exist a
12

ba.^ .ab1 (modn).^Inmult indana(modn) cubobt ineman11 (modn).
2.)3. Presupunem c a n=pe1
1
:::
pet
t,p1; :::; ptnumere prime, pi6=pj, pentrui6=j
 siej1. Dac ane par, iaua=1 de unde avem c a ( 1)n11 (modn) adic a (1)1
(modn) de aici rezult a c a n11 (modn) decin= 2 -contradic t iec acine compus.
Deoareceneste impar, ecare pje impar. Ar at c a ej= 1, pentru orice j2f1;:::;tgde
unde rezult a c a ne liber de p atrate. Fie ajr ad acin a primitiv a modulo pej
j8j2f1;


; tg.
Deci sistemul:
8
>>>><
>>>>:xa1(modpe1
1)
xa2(modpe2
2)
:::::::::::::::::::::::::::
xat(modpet
t)
are solut ie unic a modulo nconform lemei chineze a resturilor deoarece ( pej
j; pei
i) = 18i6=j.
Fieaaceast a solut ie, deci aaj(modpej
j)  si (a; pej
j) = 1 rezult a c a ( a; n) = 1  si conform
ipotezei 2 avem c a an11 (modn).
Deoarecean11 (modn) avem c an=pe1
1
:::
pet
tjan11)pej
jjan11)an11
(modpej
j). Deducem c a an1
j1 (modpej
j), dar conform denit iei 1.20a(pej
j)
j1
(modpej
j))(pej
j)jn1)pej1
j
(pj1)jn1.
Dac aej>1)pjjn sipjjn1  si prin sc adere avem c a pjj1 -contradic t iec acipj>1, deci
ej= 1)pj1jn1.
3.)1. Fien=p1
:::
pt,pi- prime  sipi1jn1. Fiea2Z, ar at c aana(modpj)
de unde avem c a ana(modn) conform lemei chineze a resturilor .
Fiej- xat. Dac a ( a; pj) = 1)apj11 (modpj), darpj1jn1)an11
(modpj))ana(modpj). Dac a (a; pj)>1)pjja)ana0 (modpj) . 
Exemplu
Folosind criteriul lui Korselt este foarte u sor s a veric am dac a un num ar este Carmichael.
De exemplu 561 = 3
11
17 este cel mai mic num ar Carmichael, evident e liber de p atrate
 si 560 este divizibil cu 2, 10  si 16.
1.4 Teorema lui Scherk  si postulatul lui Bertrand (demonstrat de
Ceb^  sev)
^In anul 1845 Bertrand sust ine c a pentru orice num ar natural nmai mare strict ca 3 exist a
un num ar prim pastfel ^ nc^ at p2(n;2n2), iar ^ n 1830 H. F. Scherk arm a c a : pentru
orice num ar n2Nexist a o alegere convenabil a a semnelor +  si astfel ^ nc^ at s a aib a loc
egalit at ile:
p2n= 1p1p2:::p2n2+p2n1
13

p2n+1= 1p1p2:::p2n1+ 2
p2n:
Vom demonstra cele dou a rezultate urm arind prezentarea f acut a de L. Panaitopol  si A.
Gica din \Probleme celebre de teoria numerelor" , editura Universit at ii din Bucure sti, 1998,
pagina 138.
Lem a 1.2 Fie(qn)n2Nun  sir strict cresc ator de numere naturale av^ and propriet at ile:
1
q1= 2; q2= 3; q3= 5; q4= 7; q5= 11; q6= 13; q7= 17:
2
qneste impar;8n2N; n2:
3
qn+1<2
qn;8n2N:
Pentru orice num ar natural n; n3 si orice num ar natural impar mai mic sau egal cu
q2n+1exist a o alegere a semnelor + siastfel ^ nc^ at num arul impar mai mic sau egal cu
q2n+1s a se scrie sub forma:
q1q2:::q2n1+q2n:
Demonstrat ie: FieP(n) : Pentru orice num ar natural n; n3  si orice num ar
natural impar mai mic sau egal cu q2n+1exist a o alegere a semnelor +  si astfel ^ nc^ at
num arul impar mai mic sau egal cu q2n+1s a se scrie sub forma:
q1q2:::q2n1+q2n
I.P(3) : Ar at c a orice num ar natural impar mai mic sau egal cu q7= 17 se poate scrie sub
forma :
235711 + 13
de unde rezult a c a P(3) e adev arat a.
1 =2 + 3 + 5711 + 13 =q1+q2+q3q4q5+q6
3 = 235 + 711 + 13 =q1q2q3+q4q5+q6
5 = 2 + 3 + 5711 + 13 =q1+q2+q3q4q5+q6
7 =2357 + 11 + 13 =q1q2q3q4+q5+q6
9 = 2 + 35 + 711 + 13 =q1+q2q3+q4q5+q6
11 = 2357 + 11 + 13 = q1q2q3q4+q5+q6
13 = 23 + 5 + 711 + 13 =q1q2+q3+q4q5+q6
15 =2 + 3 + 5 + 711 + 13 =q1+q2+q3+q4q5+q6
17 = 2 + 357 + 11 + 13 = q1+q2q3q4+q5+q6
II.P(n))P(n+ 1)
S tim c aP(n) e adev arat a. Fie 2 k1 un num ar natural impar mai mic sau egal cu q2n+3.
14

Avem c a :
q2n+2<2k1q2n+2<q 2n+2 (1)
Prima parte a inegalit at ii (1) este evident a deoarece :
0<2k1)q2n+2<2k1q2n+2:
Pentru a demonstra a doua parte a inegalit at ii (1) vom folosi condit ia 3
din ipotez a
2k1q2n+3<2q2n+2)2k1q2n+2<q 2n+2:
Exist a deci o alegere a semnului + sau astfel ^ nc^ at
0(2k1q2n+2)<q 2n+2:
Folosind din nou condit ia 3
din ipotez a, deducem c a :
q2n+1(2k1q2n+2)q2n+1<q 2n+1:
Deoarece
(2k1q2n+2)<q 2n+2<2q2n+1
exist a o alegere a semnelor + sau astfel ^ nc^ at:
0[(2k1q2n+2)q2n+1]q2n+1 (2):
Folosind condit ia 2
din ipotez a avem c a q2n+1 siq2n+2sunt impare deci  si termenul din
mijlocul egalit at ii (2) este impar  si folosind ipoteza de induct ie exist a o alegere a semnelor
+  siastfel ^ nc^ at
[(2k1q2n+2)q2n+1] =q1q2:::q2n1+q2n:
De aici avem c a
2k1 =q1q2:::q2n+1+q2n+2
deciP(n+ 1) e adev arat a . 
Lem a 1.3 Pentru orice num ar natural n2avem :
Cn
2n>4n
2pn
Demonstrat ie:
Fie
P(n) :Cn
2n>4n
2pn
15

I.
P(2) :C2
4>42
2p
2
P(2) : 6>4p
2
II.
P(n))P(n+ 1)
P(n) :Cn
2n>4n
2pn
P(n+ 1) :Cn+1
2n+2>4n+1
2pn+ 1
Cn+1
2n+2=(2n+ 2)!
(n+ 1)! (n+ 1)!=(2n+ 2)(2n+ 1)
(n+ 1)(n+ 1)
Cn
2n=2(2n+ 1)
n+ 1
Cn
2n>2(2n+ 1)
n+ 1
4n
2pn=
=2(2n+ 1)
4n
p
n(2n+ 2)2=2(2n+ 1)
4n
p
n(4n2+ 8n+ 4)=2(2n+ 1)
4n
p
4n3+ 8n2+ 4n=2(2n+ 1)
4n
p
(n+ 1)(4n2+ 4n)=
=2(2n+ 1)
4n
pn+ 1
p
4n2+ 4n>2p
4n2+ 4n
4n
pn+ 1
p
4n2+ 4n>2
4n
pn+ 1=4
4n
2pn+ 1=4n+1
2pn+ 1:
Am folosit inegalitatea 2 n+ 1>p
4n2+ 4nind adev arat a deoarece (2 n+ 1)2= 4n2+
4n+ 4 . 
Lem a 1.4 FiePn1produsul numerelor prime mai mici sau egale cu n1, unden1
este un num ar natural diferit de 0, atunciPn1<4n1:
Demonstrat ie:
Fie
P(n1) :Pn1<4n1;8n2
I.
P(1) :P1= 1<41
II.
P(n1))P(n)
S timP(n1) vrem s a ar at am P(n).
Cazul 1: Dac a n este par atunci Pn=Pn1<4n1<4n:
Cazul 2: Dac a n= 2k+ 1,k2Natunci orice num ar prim pdin [k+ 2;2k+ 1] divide
num arulCk
2k+1, c aci
Ck+1
2k+1=(2k+ 1)
2k
(2k1)
:::
(k+ 2)
(k+ 1):::
1
k!
(k+ 1)!=(2k+ 1)
2k
(2k1)
:::
(k+ 2)
k!
prin urmare  si produsul lor divide Ck
2k+1. Conform binomului lui Newton
(x+y)n=nX
t=0Ct
n
xnt
yt
16

(1 + 1)n=nX
t=0Ct
n
(1 + 1)2k+1=2k+1X
t=0Ct
2k+1=C0
2k+1+


+C2k+1
2k+1
C0
2k+1+


+C2k+1
2k+1>Ck
2k+1+Ck+1
2k+1= 2
Ck
2k+1
prin urmare Ck
2k+1<4k si din ipoteza de induct ie  stim c a Pk+1<4k+1de undePn=P2k+1
Pk+1
Ck
2k+1<4k+1
4k= 42k+1= 4n:
Teorem a 1.15 (Legendre) Fie nnum ar natural  si pnum ar prim atunci exponentul lui
p^ n descompunerea ^ n factori primi a lui n!este egal cu
n
p
+n
p2
+n
p3
+::::
Demonstrat ie:
^In suma de mai sus un num ar nit de termeni sunt nenuli deoarece exist a t02Nastfel
^ nc^ atpt0>nde unde avemh
n
pii
= 08it0; i2N:
Num arul numerelor naturale nenule mai mici ca n si divizibile cu peste egal cuh
n
pi
Num arul numerelor naturale nenule mai mici ca n si divizibile cu p2este egal cuh
n
p2i
Num arul numerelor naturale nenule mai mici ca n si divizibile cu p3este egal cuh
n
p3i
etc. .
De aici avem c a exponentul lui p^ nn! este
n
p
+n
p2
+n
p3
+::::
Exemplu (exponentul lui 2 ^ n 100!)
n! = 1
2
:::
n
^Inf1;2;3; :::; 100gavem 50 =100
2
numere pare, deci divizibile cu 2.
^Inf1;2;3; :::; 100gavem 25 =100
4
numere divizibile cu 4.
^Inf1;2;3; :::; 100gavem 12 =100
8
numere divizibile cu 8.
^Inf1;2;3; :::; 100gavem 6 =100
16
numere divizibile cu 16.
^Inf1;2;3; :::; 100gavem 3 =100
32
numere divizibile cu 32.
^Inf1;2;3; :::; 100gavem 1 =100
64
num ar divizibil cu 64.
Deci exponentul lui 2 ^ n 100! este 50 + 25 + 12 + 6 + 3 + 1 = 97 :
Lem a 1.5 Dac apeste un divizor prim al lui Cn
2n sipp
2natunci exponentul lui p
^ n descompunerea in factori primi a lui Cn
2neste egal cu 1.
Demonstrat ie:
Cn
2n=(2n)!
n!
n!
17

Conform teoremei lui Legendre exponentul lui p^ n (2n)! este
2n
p
+2n
p2
+2n
p3
+::::
iar ^ nn! este n
p
+n
p2
+n
p3
+::::
deci ^ nCn
2neste egal cu
+1X
k=12n
pk
2n
pk
Cazul 1:p=p
2ndoar dac an= 2, dac a ar exista alt n6= 2 astfel ^ nc^ at p=p
2natunci
n= 2k
n1,k3 impar  sip= 4
p
2k3
n1-contradict ie c acipe prim. R am^ ane c a p= 2
de unde rezult a c a exponentul lui 2 ^ n C2
4= 6 este 1.
Cazul 2:p>p
2nde unde avem c ah
2n
pki
= 0;8k2N; k2. Deci
+1X
k=12n
pk
2n
pk
=2n
p
2n
p
Din denit ia p art ii ^ ntregi avem c a :
x1<[x]x
2n
p1<2n
p
2n
p
n
p1<n
p
n
p
deci 2n
p
2n
p
<2n
p
2n
p1
= 2:
Prin urmare exponentul lui p^ n descompunerea ^ n factori primi a lui Cn
2neste 1 c aci
1+1X
k=12n
pk
2n
pk
<2:
Lem a 1.6 Fien > 2un num ar natural, atunci nici un num ar prim pcare veric a
2
3
n<pnnu poate s a divid a Cn
2n.
Demonstrat ie:
Deoarecepveric a2
3
n<pnavem c a din2
3
n<p)2
3
n
p<1)2n
p<3  si dinpn)
p
n1)n
p1)2n
p2. Prin urmare 3 >2n
p2)h
2n
pi
= 2:
Deoarecepveric a2
3
n < pnavem c a din2
3
n < p)2
3<p
n)3
2>n
p si din
pn)1n
p. Prin urmare 1n
p<3
2)h
n
pi
= 1  sih
2n
pi
2
h
n
pi
= 22 = 0:Vreau
s a ar at c a exponentul lui pdin factorizarea Cn
2neste 0  si folosind lema 1.5 avem c a pnu
18

divideCn
2n. Dac ak2N; k2 atuncipkp2>4n2
9)2n
pk2n
p2<9
2n9
10<1. Deci
8k; n2N; k2; n5;2n
3< pnavem c ah
2n
pki
2
h
n
pki
= 0. R am^ ane de vericat
pentrun= 3  si pentru n= 4. Dac an= 3 saun= 4 atunci p= 3 care nu convine deoarece
nu divideC3
6 si niciC4
8.
Lem a 1.7 Exponentul num arului prim p^ n factorizarea lui Cn
2neste egal cu 1dac a
n<p< 2n:
Demonstrat ie:
Deoarecen<p)2n<2p)2n
p<2  si dinp<2n)1<2n
p, deci 1<2n
p<2  sih
2n
pi
= 1:
A sadar avem c ah
2n
pi
2
h
n
pi
= 1 (c acin < p  sih
n
pi
= 0) . Dac a k2; k2Navem c a
2n
pk2n
p2<2
p<2
n, iar dac a lu am n2 deducem c ah
2n
pki
2
h
n
pki
= 0  si folosind lema 1.5
demonstrat ia este ^ ncheiat a. 
Lem a 1.8 (n)n
218n2N; n14(unde(n)reprezint a num arul numerelor
prime mai mici sau egale cu n) .
Demonstrat ie:
Cazul 1:n= 14)(14) =14
21 = 6
Cazul 2:n15; n2Natunci numerele 1 ;9;15;4;6;8;10; :::; 2
n
2
sunt mai mici
sau egale cu nsi nu sunt prime, de aici avem c a (n)n
3 +n
2
1

=n2n
2
<
n2n
21

=n
21:
Lem a 1.9 FieRnprodusul numerelor prime pcare veric a n<p2natunci
Rn>4n
3
2
pn
(2n)p
n=28n98
iar dac a nu avem pprim astfel ^ nc^ at p2(n;2n]atunci consider am c a Rn= 1:
Demonstrat ie:
DeoareceCn
2n=(n+1):::(2n1)2n
n!rezult a c aRnjCn
2nde unde avem c a exist a Qn2Nastfel
^ nc^ atCn
2n=Rn
Qn. Din lema 1.7 avem c a orice num ar prim pcare veric a n < p < 2n
 si care divide Cn
2nare exponentul 1  si cum Rncont ine toate numerele prime din ( n;2n]
avem c a orice divizor prim a lui Qneste mai mic sau egal cu n si din lema 1.6 deducem c a
orice divizor prim pa luiQntrebuie s a e mai mic sau egal cu2n
3:Fieqnum ar prim, dac a
qrjCn
2n, atunciqr2n. Presupunem prin reducere la absurd c a qr>2nde aici rezult^ and
c ah
2n
qki
= 0 pentru orice kr si deci exponentul lui q^ nCn
2neste egal cu
r1X
k=12n
qk
2n
qk
r1
contradict ie c aci exponentul lui qesterdeciqr2n^ n demonstrat ie am folosit  si c a
[2t]2 [t]<2t2(t1) = 21;8t2R. Dac a exponentul unui num ar prim pdin
19

factorizarea lui Qnrespectiv a lui Cn
2neste mai mare strict ca 1 atunci din lema 1.5 avem c a
p<pn. PeQnpot s a-l scriu ca An
BnundeAn; Bn2N;(An;Bn) = 1,Aneste produs
de numere prime diferite, iar Bnare proprietatea c a orice num ar qcare divide Bntrebuie
s a verice  si q2jBn. Am ar atat c a orice divizor prim a lui Qneste2n
3, din lema 1.4  si din
modul de construct ie a lui Anavem c a
AnP[2n
3]<4[2n
3]42n
3(1):
Am ar atat c a dac a qeste prim  si qrjCn
2natunciqr2nsi din modul de construct ie a lui Bn
(exponentul oricarui num ar din factorizarea lui Bneste mai mare strict ca 1) avem aplic^ and
lema 1.5 c a p<p
2n si
Bn(2n)([p
2n])(2):
Deoarecen98 avem c ap
2n
14  si aplic^ and lema 1.8 avem
hp
2ni
p
2n
21<p
2n
2=rn
2(3):
Folosind (1) ;(2)  si (3) rezult a c a pentru n98
Qn=An
Bn<42n
3
(2n)pn
2
 si t in^ and cont  si de lema 1.3 avem
4n
2pn<Cn
2n=Rn
Qn<Rn
42n
3
(2n)pn
2
de unde avem
Rn>4n
3
2
pn
(2n)p
n=28n98:
Lem a 1.10 Pentru orice k8natural avem 2k>18 (k+ 1)  si pentru orice x8real
avem 2x>18x.
Demonstrat ie: Induct ie dup a k.
Fie
P(k) : 2k>18 (k+ 1)8k8
I.
P(8) : 28= 256>18
9 = 162
II.
P(k))P(k+ 1)
2k+1= 2k
2>36(k+ 1)>18k+ 36 = 18( k+ 2). Dac a x2R; x8 atunci folosind
[x] + 1>xavem 2x2[x]>18([x] + 1)>18x: 
20

Lem a 1.11 Pentru orice k6natural avem 2k>6 (k+ 1)  si pentru orice x6real
avem 2x>6x.
Demonstrat ie:
Din lema 1.10 avem c a 2k>18 (k+ 1))2k>18 (k+ 1)>6 (k+ 1)8k8 r am^ ane de
vericat pentru k= 6  si pentru k= 7. Evident 26= 64>6
7 = 42  si 27= 128>6
8 = 48:
Dac ax2R; x6 atunci folosind [ x] + 1>xavem 2x2[x]>6([x] + 1)>6x: 
Lem a 1.12 Rn>2n;8n2N; n648:
Demonstrat ie:
Din lema 1.9 avem c a Rn>4n
3
2
pn
(2n)p
n=28n98 deci este sucient s a ar at c a 4n
3>
4npn
(2n)pn
2;8n2N; n648:Deoarecen648 avem c ap
2n
62
18
6= 6  si conform
lemei 1.11 avem c a 2p
2n
6>p
2n si ridicand aceast a inegalitate la putereap
2navem c a
2n
3>(2n)pn
2 (1):
Deoarece2n
9>88n648 putem aplica lema 1.10  si obt inem 22n
9>18
2n
9= 4nde unde
rezult a
2n
3>4np
4n>4npn(2):
Din (1)  si (2) avem 4n
3>4npn
(2n)pn
2:
Lem a 1.13 Fien2N; n648atunci exist a cel put in dou a numere prime mai mari
strict cansi mai mici ca 2n.
Demonstrat ie:
Presupunem prin reducere la absurd c a exist a un num ar prim care veric a ipoteza atunci
Rn2n, dar din lema 1.12 avem c a Rn>2n. Presupunerea f acut a este fals a prin urmare
exist a cel put in doua numere prime ^ n ( n;2n]:
Lem a 1.14 Fien>5,n2Natunci exist a cel put in dou a numere prime p^ n(n;2n].
Demonstrat ie:
Trebuie s a demonstr am enunt ul pentru n2N;6n647 deoarece cazul n>647 a fost
demonstrat ^ n lema 1.13 . Pentru n= 6 armat ia este adev arat a c aci 7 ;112(6;12]:Fie
secvent a de numere naturale prime : 7, 11, 13, 19, 23, 37, 43, 73, 83, 139, 163, 277, 317,
547, 631, 653, 1259. Aceste numere veric a inegalitatea qk+2<2
qk80< k < 16. Fie
n2N;6<n< 648 atunci exist a un unic k2N; k15 astfel ^ nc^ at qkn<qk+1. Din
qk+2<2
qk2ndeducem c a ^ ntre n si 2nse a
 a cel put in dou a numere prime  si anume
qk+1 siqk+2:
Teorem a 1.16
pk+1<2pk;8k2N
21

Demonstrat ie:
Dac ak4 atuncipkp4= 7>5  si aplic^ and lema 1.14 ^ ntre pk si 2
pkexist a cel put in
dou a numere prime adic a pk+1 sipk+2de unde avem c a pk+1<2
pk, r am^ ane de vericat
armat ia pentru 0 <k< 4. Evident c a 3 = p2<4 = 2
2 = 2
p1, 5 =p3<6 = 2
3 = 2
p2,
7 =p4<10 = 2
5 = 2
p3de unde avem c a
pk+1<2pk;8k2N:
Teorem a 1.17 (Ceb^  sev) Pentru orice num ar natural nmai mare strict ca 3exist a un
num ar prim pastfel ^ nc^ at p2(n;2n2):
Demonstrat ie:
Din lema 1.14 avem c a 8n2N; n > 5 exist a dou a numere prime p siqastfel ^ nc^ at
n < p < q < 2n)n < p2n2, dar 2n2 este compus  si peste prim de unde avem
c an<p< 2n2, r am^ ane de vericat cazul n= 4  sin= 5, dac an= 4, atunci ^ ntre 4  si
6 avem num arul prim 5, iar dac a n= 5 avem c a ^ ntre 5  si 8 exist a num arul prim 7, prin
urmare teorema este demonstrat a. 
Teorem a 1.18 (Scherk) Pentru orice num ar n2Nexist a o alegere convenabil a a
semnelor + siastfel ^ nc^ at s a aib a loc egalit at ile:
p2n= 1p1p2:::p2n2+p2n1 (i)
p2n+1= 1p1p2:::p2n1+ 2
p2n (ii)
Demonstrat ie:
Pentru egalitatea ( ii) observ am ca  si pentru egalitatea ( i) c a  sirul numerelor prime ( pn)n2N
veric a cele trei condit ii din lema 1.2 primele dou a condit ii sunt evident vericate, iar
folosind teorema 1.16 este vericat a  si condit ia a treia. Pentru n3,p2n+1p2n1
veric a cerint ele din lema 1.2 de unde avem c a exist a o alegere a semnelor +  si astfel
^ nc^ atp2n+1p2n1 =p1p2:::p2n1+p2n, egalitatea ( ii) este demonstrat a pentru
n3, iarp3= 5 = 12+2
3 = 1p1+2
p2 sip5= 11 = 12+35+2
7 = 1p1+2
p2
adic a egalitatea ( ii) este vericat a pentru n2N. Pentrun3,p2n+2p2n+11 veric a
cerint ele din lema 1.2 de unde avem c a exist a o alegere a semnelor +  si astfel ^ nc^ at
p2n+2p2n+11 =p1p2:::p2n1+p2n, egalitatea ( i) este demonstrat a pentru
n4, iarp2= 3 = 1 + 2 = 1 + p1;p4= 7 = 12 + 3 + 5 = 1p1+p2+p3; p6= 13 =
1 + 235 + 7 + 11 = 1 + p1p2p3+p4+p5adic a egalitatea ( i) este demonstrat a
pentrun2N.
22

2 Algoritmul RSA
2.1 Criptograa
Criptograa este o  stiint a destul de veche care a luat na stere din dorint a oamenilor de
a transmite mesaje secrete  si de a comunica ecient f ar a ca alte persoane din exterior s a
cunoasc a cont inutul mesajului. Primele tentative de a trimite mesaje secrete s-au bazat
pe ascunderea efectiv a a mesajului. Un astfel de exemplu a fost semnalat de Herodot ^ n
scrierile sale. Acesta, relat^ and luptele dintre greci  si persani, ment ioneaz a cum numai arta
scrierii secrete a salvat Grecia de furia armatei persane, atunci c^ and elenii nu i-au trimis
daruri lui Xerxes, Regele Regilor. Ace stia sunt informat i de Demaratos, un grec exilat ^ n
ora sul persan Susa care r am asese loial t  arii sale, printr-un mesaj ascuns. Neav^ and cum s a
trimit a o scrisoare, acesta a ^ ndep artat ceara de pe o t ablit  a, a scris mesajul pe lemn  si a
acoperit t ablit a cu cear a. Init ial grecii nu au  stiut ce s a fac a cu t ablit a p^ an a c^ and sot ia lui
Leonidas, Gorgo,  si-a dat seama c a mesajul era acoperit cu cear a. Datorit a acestui mesaj
grecii au ie sit victorio si chiar ^ n ziua atacului, ^ n data de 23 septembrie 480 i.Hr.. Astfel a
ap arut steganograa, de si aceasta este o tehnic a rudimentar a de ascundere a mesajului a fost
des folosit a ^ n primele secole. Aparit ia criptograei era absolut necesar a deoarece ^ n cazul
steganograei mesajul odat a descoperit putea  descifrat cu usurint a. A sadar criptograa
are rolul de a face mesajele nedescifrabile.
O serie de mesaje ascunse ^ n cateva opere celebre ale lui Platon au fost descoperite de
un profesor din Marea Britanie. Aceste texte au fost analizate timp de 2000 de ani de
cele mai luminate mint i, ^ ns a, se pare c a aceste opere mai au totu si secrete. Dup a p arerea
profesorului Jay Kennedy, una dintre cele mai importante teorii a lui Platon este ascuns a ^ n
textele sale : \ Operele lui Platon au jucat un rol major ^ n aparit ia culturii occidentale, ^ ns a
ele sunt misterioase  si se ^ ncheie prin ghicitori. ^In Antichitate, mult i dintre discipolii lui au
declarat c a operele sale cont in o serie de coduri secrete, ^ ns a aceast a teorie a fost respins a de
savant ii din epoca modern a. Este o poveste veche  si lung a, ^ ns a eu am reu sit s a sparg acest
cod. Am dovedit faptul c a operele sale cont in ^ ntr-adev ar coduri  si simboluri, iar descifrarea
lor va conduce la descoperirea losoei secrete a lui Platon \. Profesorul a descoperit c a
frazele, temele  si cuvintele folosite de Platon sunt desp art ite de intervale regulate, acestea
coincid cu spat iile dintre cele 12 note muzicale ale portativului grec.
^In 1918, inventatorul german Arthur Scherbius a construit o ma sin a criptograc a care
avea la baz a discul de cifrare creat ^ n secolul al XV-lea. Aceast a ma sin a a fost numit a
Enigma  si a devenit ^ ntr-un timp foarte scurt cel mai temut sistem de criptare din istorie.
Algoritmul criptograc al ma sinii avea la baz a o substitut ie polialfabetic a complex a,
realizat a cu ajutorul a trei discuri mobile. Ca  si alte ma sini cu rotoare, Enigma este o
combinat ie de sisteme mecanice  si electrice. Cu ajutorul acestei ma sini, expeditorul putea
s a tasteze textul, iar ma sina genera mesajul criptat. Destinatarul avea  si el o ma sin a Enigma
 si un exemplar al c art ii de coduri, tasta textul cifrat pentru a genera mesajul init ial. Eroul
luptelor cu Enigma a fost matematicianul Alan Turing, care a dezvoltat concept ia polonez a
23

Figure 2: Enigma
a \ bombelor criptologice \, pentru a sparge cifruri complexe. Primul dispozitiv proiectat
de el, \ Victory \ a ^ nceput s a e folosit ^ nc a din martie 1940. P^ an a la sf^ ar situl r azboiului,
la Bletchley Park au fost realizate aproximativ 200 de dispozitive care ajutau la descifrarea
set arilor rotoarelor  si mesajelor cheie criptate cu ajutorul Enigmei. Cercet arile lui Turing
au dus la construirea primei ma sini programabile numit a Colossus.
^Intr-un secol^ n care informat ia este indipensabil a, asigurarea securit at ii acesteia devine o
preocupare de prim rang. Securitatea ^ nseamn a protect ie ^ n fat a unei eventuale amenint ari,
amenint  arile pot varia de la simpla modicare a informat iei p^ an a la accesarea de c atre
persoane neautorizate  si distrugerea acesteia. Dezvoltarea tehnicilor criptograce ^ n general
a fost motivat a de incidente, de cele mai multe ori de incidente cu urm ari negative. Primul
atac informatic a avut loc^ n 1982, c^ and spionii sovietici au furat un software de la o companie
din Canada. Agent ii sovietici nu au intuit c a speciali stii CIA au introdus ^ n software o \
bomb a logic a \ adic a ni ste linii de cod care ^ n anumite condit ii activeaz a o funct ie. Bomba
logic a a condus la o explozie masiv a care a avut loc l^ ang a o conduct a de gaz din Siberia.
Explozia a fost at^ at de puternic a ^ nc^ at a fost detectat a de satelit ii americani din spat iu.
Cea mai sosticat a arm a cibernetic a ce a ie sit p^ an a acum la iveal a este Stuxnet, un vierme
informatic ce a fost folosit pentru a ^ nt^ arzia programul nuclear iranian cu aproximativ doi
ani. Despre Stuxnet se crede c a a fost creat ^ n urma colabor arii dintre americani  si israelieni.
Stuxnet a fost analizat de speciali sti din domeniu care au r amas impresionat i, ind cel mai
ingenios  si complex vierme informatic descoperit vreodat a. Microsoft estimeaz a c a au fost
necesare aproximativ 10.000 de zile pentru realizarea Stuxnet.
Criptograa reprezint a o ramur a a matematicii care se ocup a cu securizarea informat iei,
precum  si cu autenticarea  si restrict ionarea accesului ^ ntr-un sistem informatic. Termenul
provine din cuvintele grece sti kryptos care ^ nseamn a a ascunde  si graphein care ^ nseamn a a
24

scrie .
Situat ia general a de care se ocup a criptograa este urm atoarea:
Expeditorul (numit Alice) dore ste s a trimit a destinatarului (numit Bob) un mesaj printr-
un canal de comunicat ie nesigur. Acest canal este nesigur deoarece un adversar (numit
Oscar) dore ste din diferite motive s a cunoasc a sau s a modice mesajul.
Aceast a condent ialitate solicitat a de Alice  si Bob se rezolv a de cele mai multe ori prin
modicarea mesajului ^ n a sa fel ^ nc^ at s a nu poat a  ^ nt eles de Oscar. Aceast a transformare
a mesajului se num ste criptare.
Denit ie 2.1 Se nume ste criptosistem un 5-uplu (M;C;K;E;D)nevide unde:
M spat iul textelor simple
C spat iul textelor criptate
K spat iul cheilor
E=fEe:M!Cje2Kg spat iul funct iilor de criptare
D=fDd:C!Mjd2Kg spat iul funct iilor de decriptare
Subliniem faptul c a: 8e2K,9d2K astfel ^ nc^ at Dd(Ee(m)) =m.Cheilee sidse numesc
pereche de chei si se noteaz a ^ n general ( e; d) .
Criptosistemele pot  clasicate ^ n criptosisteme simetrice  si criptosisteme asimetrice.
2.2 Criptosisteme simetrice (criptosisteme cu cheie secret a)
Se nume ste criptosistem simetric un criptosistem pentru care cheia de decriptarea este egal a
cu cheia de criptare sau se poate obt ine u sor din aceasta. Se nume ste criptosistem "perfect
sigur" dac a Oscar nu poate ^ nv at a nimic dintr-un text criptat interceptat presupun^ and
c a are la dispozit ie cel mai puternic sistem de calcul. Criptosistemele simetrice prezint a
urm atoarele avantaje :
cheile sunt relativ scurte
pot transmite volume mari de date
prin compunere pot duce la sisteme de criptare puternice
FieSo mult ime nevid a  si nit a. Atunci :
i. dac aAS atunciAeste un eveniment al lui S.
ii. dac aa2Satunciaeste un eveniment elementar al lui S.
iii.P(S) reprezint a mult imea tuturor evenimentelor lui S:
Denit ie 2.2 Se nume ste distribut ie a probabilit at ii ^ n So funct ie
p:P(S)!R
astfel ^ nc^ at:
i.p(A)0;8AS
ii.p(S) = 1
iii. dac aA;BSastfel ^ nc^ at A\B=;atuncip(A[B) =p(A) +p(B)
25

Dac aASatuncip(A) se nume ste probabilitatea lui A.
Propriet at i:
1.p(;) = 0
2.AB)p(A)p(B)
3.8AS)p(SnA) = 1p(A)
4.p(A)2[0;1]8A
5.A1; A 2; :::AnS,Ai\Aj=; 8i6=j)p([n
i=1) =Pn
i=1p(Ai)
6.AS; p(a) =p(fag); a2A;iarp(A) =P
a2Ap(a)
Denit ie 2.3 FieSun spat iu de modelare pe care este dat a o distribut ie a probabilit at ii
p. Dac ap(a) =1
card(S)pentru orice a2Satuncipse nume ste distribut ie uniform a.
Denit ie 2.4 FieA; BSdou a evenimente ale lui S sipo distribut ie a probabilit at ii
dat a peS. Dac ap(B)>0, probabilitatea lui Acondit ionat a (de realizarea lui B) sau
probabilitatea ca evenimentul As a se realizeze ^ n ipoteza c a evenimentul Bs-a ^ nt^ amplat
(p(B)6= 0) este denit a prin:
p(AnB) =p(A\B)
p(B):
Observat ie 2.1 Aplicat iap(jB) :A!R,p(ajB) =p(fagjB)este o probabilitate pe
Apentru c a avem 😛
a2Ap(ajB) =P
a2Bp(ajB) =P
a2Bp(a)jp(B) = 1 .
Denit ie 2.5 Dou a evenimente se zic independente dac a p(A\B) =p(A)
p(B).
Teorem a 2.1 (Bayes) Dac a A; B sunt evenimente cu p(A)>0; p(B)>0atunci
p(B)
p(AnB) =p(A)
p(BnA)
Demonstrat ie: Evident
p(A\B) =p(AnB)
p(B) (1)
p(A\B) =p(BnA)
p(A) (2):
Din (1)  si (2) avem c a
p(B)
p(AnB) =p(A)
p(BnA):
Fie (M;C;K;E;D) un criptosistem simetric. Pe Mdenim o distribut ie a probabilit at ii
pMastfel ^ nc^ at pM(m)>0;8m2M . Se presupune c a Oscar  stie limba folosit a de Alice  si
de Bob. PeKdenim o distribut ie a probabilit at ii pKastfel ^ nc^ at pK(k)>0;8k2K. Pe
spat iul produsMK probabilit at ile pM sipKinduc o distribut ie a probabilit at ii pMK.
A sadar pentru orice mesaj necriptat m si orice cheie kavem c a probabilitatea ca textul ms a
e criptat cu cheia keste dat a de pMK(m; k ) =pM(m)
pK(k). PeCdenim o distribut ie
26

a probabilit at ii pCastfel ^ nc^ at pC(c)>0;8c2C. Fiem2M , denim evenimentul ~ mastfel
~m=f(m; k )jk2KgMK . Probabilitatea ca mesajul ms a e criptat este dat a de
pMK( ~m) =X
(m;k)2~mpMK(m; k ) =X
k2KpM(m)
pK(k)
de unde avem c a:
pMK( ~m) =pM(m):
Fiek2K, denim evenimentul ~kastfel ~k=f(m; k )jm2MgMK . Probabilitatea
ca s a e folosit a cheia keste dat a de
pMK(~k) =X
(m; k )2~kpMK(m; k ) =X
m2MpM(m)
pK(k)
de unde avem c a:
pMK(~k) =pM(k):
Observ am c a evenimentele ~ m si~ksunt independente deoarece p( ~m\~k) =p(m; k ) =p(m)

p(k) =p( ~m)
p(~k):Fiec2C, denim evenimentul ~ castfel ~c=f(m; k )jEk(m) =cgMK .
Denit ie 2.6 Un criptosistem este perfect secret dac a pentru orice text simplu m2M
 si orice text cifrat c2C avem
pMK( ~mn~c) =pM(m):
Propozit ie 2.1 Fie(M;C;K;E;D)un criptosistem perfect secret. Atunci cardK
cardM:
Demonstrat ie: Fiec12Cxat. Vom ar ata c a 8m2M;9k2Kastfel ^ nc^ at Ek(m) =c1.
Presupunem prin reducere la absurd c a 9m12M astfel ^ nc^ at8k2K; Ek(m1)6=c1de
unde avem c a ~ m1\~c1=f(m1;k)jEk(m1) =c1g=;adic ap( ~m1\~c1) = 0  sip( ~m1n~c1) =
p( ~m1\~c1)
p( ~c1)= 0:Criptosistemul este perfect secret deci p( ~m1n~c1) =p(m1)  si cump( ~m1n~c1) = 0
avem c ap(m1) = 0-contradict ie cu faptul c a p(m1)>0:Consider amK=fk1; k2; :::; klg
 siM=fm1; m 2; :::mngastfel ^ nc^ at l < n . Fiemi; mj2M astfel ^ nc^ at mi6=mj. Am
ar atat c a pentru orice text simplu mexist a o cheie kastfel ^ nc^ at Ek(m) =c1. Deoarece
cardK< cardMatunci presupunem c a mi simjsunt criptate cu aceea si cheie kadic a
Ek(mi) =Ek(mj) =c1:Dar aplic^ and acum funct ia de decriptare obt inem c a mi=mj-
contradict ie ( mi6=mj). Am ar atat c a cardKcardM:
Teorem a 2.2 (Shannon) Fie criptosistemul (M;C;K;E;D)astfel ^ nc^ at cardK=
cardM=cardC si peM;C;Kavem distribut ii nenule ale probabilit at ilor . Atunci cripto-
sistemul este perfect secret dac a  si numai dac a urm atoarele condit ii sunt satisf acute:
i
Distribut ia probabilit at ilor pe spat iul cheilor este cea uniform a, adic a orice cheie este
aleas a cu aceea si probabilitate .
27

ii
Pentru orice text simplu m2M  si pentru orice text cifrat c2C exist a o unic a cheie
k2K astfel ^ nc^ at Ek(m) =c.
Demonstrat ie:
)Demonstr am ii
. S tim c a criptosistemul ( M;C;K;E;D) este perfect secret  si aplic^ and
propozit ia 2.1 avem c a cardKcardMadic a pentru orice text cifrat c si pentru orice
text simplu m, exist a o cheie k2K astfel ^ nc^ at Ek(m) =cde aici avem existent a .
Funct iaf:K!C denit a prin f(k) =Ek(m0) pentru un mesaj m0xat este surjectiv a.
Dar conform ipotezei avem c a cardK=cardCceea ce implic a  si injectivitatea funct iei, a sa
^ nc^ at avem  si unicitatea .
Demonstr am i
Fiec0un text cifrat xat. Presupunem cardK=n siM=fm1;m2;:::;mng.
Etichet am cheilefk1;k2;:::;kngastfel^ nc^ at pentru orice i2f1;2;:::;ngavemEk(mi) =c0.
Indexarea poate  f acut a datorit a punctului ii
, c aci prin xarea lui c0, avem c a pentru orice
mexist a o unic a cheie kastfel ^ nc^ at Ek(m) =c0, deci pentru ecare miasociem cheia ki.
Observ am c a aceast a indexare acoper a toate cheile . Dac a pentru dou a mesaje diferite
mi6=mj, ar exista o aceea si cheie kastfel ^ nc^ at Ek(mi) =Ek(mj) =c0atunci decriptarea
nu ar mai putea avea loc deoarece Ekeste injectiv a . Folosind asocierea de mai sus, teorema
lui Bayes  si faptul c a criptosistemul este perfect secret avem c a :
p( ~mi) =p( ~mi=~c0) =p( ~c0=~mi)
p( ~mi)
p( ~c0)=p(~ki)
p( ~mi)
p( ~c0):
S tim c a pentru orice text simplu mavemp(m)>0 decip(ki) =p(c0) pentru orice i2
f1;2;:::;ngde unde avem c a distribut ia probabilit at ii pe spat iul cheilor este uniform a .
(Presupunem c a sunt adev arate condit iile i
 siii
 si demonstr am c a criptosistemul este
perfect secret. Pentru un text simplu m si un text cifrat c, ek=k(m;c) unica cheie astfel
^ nc^ atEk(m) =c si folosind teorema lui Bayes avem
p( ~m=~c) =p( ~m)
p(~c=~m)
p(~c)=p( ~m)
p(~k(m;c))P
q2Mp(~q)
p(~k(q;c)):
Dar cheile sunt uniform distribuite ^ n K si decip(~k(m;c)) = 1=cardK. Avem  si c a :
X
q2Mp(~q)
p(~k(m;c)) = 1=cardK
X
q2Mp(~q) = 1=cardK:
Rezult a c a p( ~m=~c) =p( ~m) pentru orice m sicadic a criptosistemul este perfect secret . 
2.3 Criptosisteme asimetrice (criptosisteme cu cheie public a)
Criptosistemele asimetrice sunt criptosistemele pentru care cheile de criptare  si de decriptare
difer a, iar metoda de criptare este public a. Schimbul de cheie Die-Hellman marcheaz a
^ nceputul criptograei cu cheie public a. Ideea a fost propus a ^ n 1976 de Die  si Hellman,
 si de si revolut ionar a, este destul de simpl a. Ideea pe care se bazeaz a este faptul c a operat ia
28

de ridicare la putere ^ n Zpeste comutativ a adic a ( xa)b= (xb)a, ^ n timp ce extragerea
logaritmului discret care presupune g asirea lui xastfel ^ nc^ at axb(mod p ) nu poate
rezolvat a ecient dac a elementele grupului au un ordin foarte mare. Algoritmul propus de
Die-Hellman este urm atorul:
1. Alice  si Bob aleg un num ar prim pfoarte mare  si o r ad acin a primitiv a gmodulop
2. Alice alege un num ar secret a si ^ i trimite lui lui Bob u=ga
3. Bob alege un num ar secret b si ^ i trimite lui Alice v=gb
4. Alice calculeaz a k=va=gab
5. Bob calculeaz a k=ub=gab
^In practic a toate criptosistemele cu cheie public a se bazeaz a e pe problema logaritmului
discret e pe problema factoriz arii ^ ntregilor. O schem a de criptare cu chei publice cont ine
urm atoarele elemente: textul clar, algoritmul de criptare, cheia public a  si cheia privat a,
textul cifrat, algoritmul de criptare.
Criptosistemele asimetrice prezint a urm atoarele avantaje :
doar cheia de decriptare trebuie t inut a secret a
sunt simplu de denit
sunt ideale pentru transmiterea informat iei prin canale nesigure.
At^ at criptosistemele simetrice c^ at  si cele asimetrice dispun de o serie de avantaje com-
plementare ceea ce face ca de cele mai multe ori s a e folosite simultan. Cu un astfel de
criptosistem hibrid se poate ^ ncepe comunicarea transmit ^ and cheia criptosistemului simetric
folosind criptosistemul asimetric urm^ and ca apoi s a e folosit criptosistemul simetric.
Criptarea cu chei publice respect a urm atoarele condit ii:
1. Emit  atorul Alice dore ste s a comunice cu receptorul Bob
2. Bob genereaz a o cheie public a e si o cheie privat a d
3. Alice,  stiind cheia public a a lui Bob  si mesajul clar M, genereaz a mesajul criptat
C=Ee(M)
4. Bob decripteaz a mesajul Castfel:
M=Dd(C) =Dd(Ee(M))
5. Un atacator care  stie cheia e si nu poate s a determine cheia privat a d
6. Un atacator care  stie textul criptat C si cheiaenu poate s a determine mesajul M
7. Are loc relat ia :
M=Dd(Ee(M)) =De(Ed(M))
Prima schem a concret a de criptare asimetric a  si semn atur a digital a a fost realizat a ^ n
anul 1977 de c atre Ron Rivest, Adi Shamir  si Len Adleman de la MIT. Schema RSA este
cea mai r asp^ andit a  si implementat a schem a din lume. Aceasta se datoreaz a ^ n primul r^ and
modalit at ii foarte simple de criptare  si de decriptare. Aparit ia RSA a fost posibil a din
urm atoarele motive:
1. Este u sor s a gener am numere prime.
29

2. Date ind dou a numere prime p siqeste u sor s a calcul am produsul lor, n=p
q.
3. Factorizarea numerelor necesit a mult timp.
4. Exponent ierea modular a se poate face u sor.
30