,,Matematicienii au încercat în zadar până acum să descopere o oarecare ordine în secvența [617405]

2

Introducere
,,Matematicienii au încercat în zadar până acum să descopere o oarecare ordine în secvența
numerelor prime, și avem motive să credem că acesta este un mister pe care mintea umană nu -l
va pătrunde. ” (Leonhard Euler)

Numerele prime au fost dintotdeauna atractive pentru matematicieni și oameni pasionați
de matematică . Parte principală a teori ei numerelor, numerele prime, deși sunt definite î ntr-un
mod simplu, au ascuns enorm de multe mistere și î ncă mai fac acest lucru.
Motivația principală pentru alegerea acestei teme este strâ ns legat ă de realitatea societății
contemporane. Faptul că avem nevoie de securitate est e un lucru cert, care ne face să căutam căi
pentru a ne construi un mediu cât mai sigu r. Deoarece o bună parte dintre schimburile de
informații și tranzactii bancare a trecut în mediul online, este clar că trebuie să gă sim metode noi
pentru a ajuta ca aceste procese să se realizeze în siguranță .
Pasiunea pentru matematică și curiozitatea m-au împins să realizez ace astă lucrare de
disertaț ie, căutând să prezint anumite concepte într -o manieră cât mai limpede și dorind să
contribui cu mici observații, aplicații și exemple personale î n acest domeniu.
Așa cum spuneam, o nevoie nativă a ființ ei umane este aceea de securit ate. De cele mai
multe ori legă m no țiunea de siguranță fizică cu un scut puternic, eventu al realizat dintr -un
material câ t ma i rezistent, iar pentru siguranța informației suntem tentați să găsim tot soiul de
parole cât mai sofis ticate. Pe de altă parte, d acă dorim să fim protejați, apelăm la un serviciu de
pază în care se află oameni bine antrenaț i, puter nici din punct de vedere fizic și mental și gata să
reacționeze în orice moment. Însă , din punct ul de vedere al securităț ii informatiei, este necesar să
găsim metode atâ t de sofis ticate care să ne protejeze sau putem să fim în siguranță chiar și
plecând de la niște raționamente banale ș i publice?
Pornind de la încercă rile lui Henri Poincare de a modela insta bilitatea sistemel or
mecanice, în anul 1960, matematicianul ș i meteorologul american Edward Lorenz introducea o
nouă ramură a matematicii și fizicii moderne denumită teoria haosului. În linii mari, această
teorie afirmă faptul că orice perturbare a condițiilor inițiale poate atrage de la sine consecinț e
extrem de greu de anticipat.
Este evident faptul că subiectul acestei teze est e acela de a trata criptografia, însă putem
să realizăm o conexiune aparentă între haos ș i criptografie. O cheie modificată, un bit greșit ș i

3
orice mică modificare a unui algoritm criptografic poat e atrage de la sine consecințe
imprevizibile ș i poate ajuta la descifrarea algoritmului.
Tot teoria haosului afirmă că “bătaia din aripi a unui fluture în București poate declanșa o
tornadă la sute de km în California“, iar acest lucru ne face să ne gâ ndim dacă putem face o
analogie cu modul în care funcționează procedeele de cri ptare considerate puternice astă zi. Un
algoritm puternic poate să fie generat inițial de “bă taia unui fluture” , flutur ele respect iv fiind un
lucru atât de banal ș i vechi de mii de ani: numerele prime.
Pornind de la această noțiune elementară, printr -un procedeu asemănător teoriei haosului,
ajungem în zilele noastre să reflectă m asupra unor idei refe ritoare la criptografia cuantică ș i
asupra unor noi direcț ii de cercetare care ne aduc un viitor mai sigur.
Lucrarea de disertație a fost gândită să se adreseze atât publicului larg cât ș i publicului de
specialitate. Evident, multe dintre rolurile numerelor prime nu au putut fi cuprinse în acest număr
de pagini, însă referinț ele bibliogr afice conduc că tre acestea pentru cei care vor să avanseze
cercetarea î n domeniu. Pornind de la teoreme clasice, lucrarea caută într -un final să trateze ș i
probleme actuale din cercetare, cu precădere partea de criptare cuantică .
În ce le ce urmează , este prezen tat pe scurt conținutul acestei lucrări de disertație ,
specificând de fiecare dată contribuț iile personale ale autorului.

Această lucrare este structurată în trei capitole după cum urmează :
1. Numerele prime și rolul lor î n criptografie
2. Testul Fermat, numere Carmichael si algoritmul El Gamal
3. Criptarea cuantică

În primul capitol am urmărit să parcurg într -un mod cronologic evoluția numerelor
prime începâ nd de la simpla definiție a unui număr prim, proprietăț i fundamentale ale num erelor
prime, celebra demonstrație a lui Eulid care justifică faptul că mulț imea numerelor prime este
infinită, o variantă modernă a demonstrației lui Euclid oferită de că tre matematicianul Hillel
Furstenberg (având la bază noțiuni de topologie), teorema fundamentală a aritmeticii, teoremele
lui Euler, Fermat, Wilson, teste de primalitate, numere Carmichael și principalele probleme
apărute î n cripto grafie legate de numerele prime : problema factor izării unui număr î ntreg, alături
de descrierea algoritmului RSA și problema logaritmului discret exemplificat prin prot ocolul de
schimb de chei Diffie -Hellman.

4
În al doilea capitol am analizat clasicul test Fermat pen tru a determina primalitatea unui
număr și am că utat printr -o metodă originală să găsesc o anumită regulă în distribuț ia numerelor
Carmichael.
O contribuție a autorului în acest capitol se regăsește prin implementarea unui algoritm
C++ care să cripteze mesaje folosind algoritmul El Gamal pe curbe eliptice, pornind de la
noțiunea de rest pătratic.
Ultimul capitol fac e referire la criptarea cuantică , domeniu actua l de interes pentru
oamenii de știință . Prima parte a capitolului se axează pe prezentarea unor noțiuni generale de
fizică cuantică, criptare cuantică ș i calculatoare cuant ice, iar a doua parte reprezintă o altă
contribuț ie a autorului , care vine cu un nou ex emplu de factorizare a unui număr î ntreg folosind
algoritmul lui Shor.
Evident, rezultatele și noțiunile teoretice regăsite în lucrare se datorează autorilor care
au fost specificați pe tot parcursul lucrării, cât și la finalul acesteia î n bibliografie, obiectivul
principal fiind o cât mai bună organizare a noț iunilor și o încercare de a căuta un punct de plecare
către noi direcț ii personale de cercetare.
Contribuțiile personale care se regăsesc în această lucrare au fost prezentate la
“Sesiunea de Comunicări Științifice Studențești” în 2017 și 2018.
Mulțumesc î n mod special domnului profesor lect. dr . Emil Simion care mi -a fost
alături î n rea lizarea acestei teze de disertaț ie, profesorilor d in Facultatea de Științe Aplicate a
Universității Politehnică din Bucureș ti pentru profesiona lismul cu care au reușit să -mi provoace
dorința de a cunoaște cât mai bine lucrurile și, î n general, persoanelor care mi -au fost alături î n
tot acest timp.

5

CAPITOLUL I
Numerele prime și rolul lor î n criptografie

1.1 Noțiuni matematice preliminare privind de primalitate a unui numă r
În cele ce urmează, prezentă m pe scurt a numite rezultate matematice fără de care
noțiunile analizate î n aceasta lucrare nu ar avea sens.

1.1.1 Definiț ie
Un numă r natural 𝑥∈ℕ se numeș te divizor natural pentru numă rul 𝑦∈ℕ, dacă
există un al numă r natural 𝑞∈ℕ astfel încâ t 𝑥𝑞=𝑦 .
Observaț ie
Pentru a scrie faptul că un numă r natural 𝑥 divide un alt numă r natural 𝑦 folosim
notaț ia 𝑥|𝑦.
Exemple : 2|6 ,5|25,11|121 𝑒𝑡𝑐.

1.1.2 Proproziț ie
Fie 𝑎,𝑏 si 𝑐 trei numere naturale nenule (eventual 𝑏>𝑐). Daca 𝑎|𝑏 si 𝑎|𝑐 , atunci 𝑎|𝑏±
𝑐.
Demonstratie:
Considerăm trei numere ca î n enunt. Cum 𝑎|𝑏 avem ca există un 𝑞∈ℕ astfel î ncat
𝑏=𝑎𝑞. Deoarece 𝑎|𝑐, există 𝑘∈ℕ astfel î ncat 𝑐=𝑎𝑘.
Prin urmare, 𝑏±𝑐=𝑎𝑞±𝑎𝑘=𝑎(𝑞±𝑘).
Ca atare, există un numă r 𝑝=𝑞±𝑘∈ℕ astfel incat 𝑎𝑝=𝑏±𝑐, ceea ce ne
conduce la finalizarea demonstraț iei.
⧠

1.1.3 Definitie (Numar prim)
Un numar natural nenul 𝑝>1 se numeste numar prim daca are exact doi divizori ( pe 1 si
𝑝)

6
Exemple: 3,5,7,31 etc.
1.1.3.1 Definiț ie:
Un număr care nu este prim se numeș te compus.
Aceste numere au fost studiate î nca din timpul matematicienilor greci. Pitagora a avut
preocupari pr ivind anumite proprietaț i interesante ale numerelor introducând noț iunea de numere
perfecte sau prietene. Ulterior, Euclid a prezen tat in celebra carte “Elemente”, două rezultate
extrem de importante privind numerele prime. Primul dintre ele est e legat de faptul că există o
infinitate de numere prime (enunțul si demonstraț ia se reg asesc în această lucrare la punctul
1.1.4) ș i al doilea rezultat cunoscut su b numele de teorema fundamentală a aritmeticii (1.1.6) .
Aceste doua rezultate stau la baza multor algoritmi puternici de criptare.
1.1.4 Teorema (Euclid)

Mulț imea numerelor prime este infinită .

Demonstraț ie :
Această teoremă veche de pes te 2000 de ani, este considerată de catre mulți
matematicieni ca avâ nd una dintre cele mai frumaose demonstrații. Î n demons tratie, apare
pentru primele dăț i metoda reducerii la a bsurd si gasirea unei contradicț ii cu ipoteza ,
combinată cu metoda repetării raț ionamentului.
Presupunem prin reducere la absurd ca mulțimea numerelor prime este finită . Fie
ea 𝑃={𝑝1,…,𝑝𝑛} astfel î ncat 𝑝𝑖 este prim si 𝑐𝑎𝑟𝑑 (𝑃)=𝑛. Considerăm numă rul 𝑁=
(∏ 𝑝𝑖𝑛
𝑖=1)+1. Dacă numarul 𝑁 este prim, atunci mulț imea 𝑃 crește cu un element și
repetând raț ionamentul ajungem la concluzie.
Dacă 𝑁 este compus , se intamplă că exista un 𝑝𝑘∈𝑃 astfel incat 𝑝𝑘|𝑁. Evident,
𝑝𝑘|𝑝1∙𝑝2∙…∙𝑝𝑛 . Folosind aceste doua relații și propoziția 1.1.2 avem că
𝑝𝑘|𝑁−𝑝1∙𝑝2∙…∙𝑝𝑛.
Prin urmare , 𝑝𝑘|1 si asta ne conduce la faptul că 𝑝𝑘=1 întrand intr -o
contradicț ie cu ipoteza deoarece 𝑝𝑘 este prim. Ca atare, 𝑁 este prim ș i multimea 𝑃 creste cu un
element.
In concluzie, mulț imea numerelor prime este infinită .
⧠

7
Acest rezultat este foarte util in studiul crip tografiei deoarece ne asigură că există numere
prime de oricate cifre dorim. Remarca aceasta o vom trata la punctul 1.2 acolo unde o să
discutăm despre problema factorizării unui numă r.

1.1.5 Teorema (Hillel Furstenberg)

Hillel Furstenberg
În cele ce urmează, prezentă m o demonstr ație mai exotică a teoreme i lui Euclid.
Această demonstraț ie a fost publicata in anul 19 55 de catre Hillel Furstenberg în timpul
studenției. Spre deosebire de demontraț ia lui Euclid, aceasta are la baza raț iuni
topologice, iar tehnica de demonstrare se axe aza pe reducere la absurd și contradicș ie.

Pe mulț imea numerelor intregi ℤ , definim o topologie generată de familia tuturor
progresiilor aritmetice, considerând submulț imea 𝑈⊂ℤ , unde 𝑈 este multime deschisă
dacă si numai dacă este vidă sau este o reuniune de progresii aritmetice 𝑆(𝑎,𝑏) , 𝑎≠0.
𝑆(𝑎,𝑏)={𝑎𝑞+𝑏|𝑞∈ℤ}=𝑎ℤ+𝑏

Reformulâ nd, 𝑈 este o mulțime deschisă dacă pentru orice 𝑥∈𝑈, există un număr
întreg nenul 𝑎 astfel încâ t 𝑆(𝑎,𝑥)⊂𝑈.
Ca atare, axiomele spaț iului topologic sunt veri ficate pentru această structura:
i) Mulșimea vidă este deschisă prin definitie, iar mulțimea ℤ se identifică cu 𝑆(1,0),
care este deschisă .
ii) Consideră m o familie de multimi deschise {𝑈𝑖} si 𝑥∈⋃𝑈𝑖𝑖, orice numar de forma
𝑎𝑖 astfel incat 𝑆(𝑎𝑖,𝑥)⊂𝑈𝑖 implică faptul ca 𝑆(𝑎𝑖,𝑥)⊂𝑈.
Prin urmare,orice reuniune de multim e deschise este multime deschisă .
iii) Pentru a arăta ca orice intersecție finită de două sau mai multe mul țimi deschise
este desch isă procedă m in felul urmator :

8
Consideră m 𝑀 si 𝑁 doua mulț imi deschise si 𝑥∈𝑀∩𝑁. Mulț imile 𝑀 si 𝑁 sunt
caracterizate de catre î ntregii 𝑎𝑚 si 𝑎𝑛. Alegâ nd 𝑎=𝑐𝑚𝑚𝑚𝑐 (𝑎𝑚,𝑎𝑛), avem ca
𝑆(𝑎,𝑥)⊂𝑆(𝑎𝑚,𝑥)⊂𝑀 si 𝑆(𝑎,𝑥)⊂𝑆(𝑎𝑛,𝑥)⊂𝑁. În concluzie, orice
intersecț ie finit ă de mulțimi desch ise este o mulțime deschisă .
În continuiare, sublinie m doua proprietăț i importante ale topologiei induse de
Furstenberg:
1. Atâta timp cât orice multime nevidă deschisă conține o infinitate de secvențe, este clar
că o mulțime finită nu poate să fie deschisă . Ca atare, complem entara unei mulțimi
finite sigur nu este inchisă, deoarece o mulțime este inchisă doar daca are
complementara deschisă , complementara complementarei fiind chiar mulțimea finită .
2. Mulț imea 𝑆(𝑎,𝑏) este atât deschisă cât ș i închisă. Faptul că este inchisa reiese din
definiț ie, iar inchiderea reiese din faptul că putem să o scriem ca fiind complementara
unei mulț imi deschise:
𝑆(𝑎,𝑏)=ℤ\⋃𝑆(𝑎,𝑏+𝑘)𝑎−1
𝑘=1
Pe de altă parte, deoarece singurele numere î ntregi care nu se pot scrie ca produs de
factori primi sunt ±1 (1.1.6), avem:
ℤ\{±1}=⋃ 𝑆(𝑝,0)
𝑝 𝑝𝑟𝑖𝑚
Folosind prim a proprietate, deducem faptul că multimea ℤ\{±1} nu poate sa fie
inchisă (deoarece este complementara unei multimi finite { -1,+1} . Din proprietate a a doua avem
că 𝑆(𝑝,0) este închisa. Dacă ar exista un numar finit de nu mere prime, atunci ar insemna că
multimea ⋃ 𝑆(𝑝,0) 𝑝 𝑝𝑟𝑖𝑚 ar fi o reuniune finita de mulțimi închise , deci închisă , ceea ce ne
conduce la o contradicț ie.
In concluzie, exist ă o infinitate de numere prime.
⧠
1.1.6 Teorema fundamentală a aritmeticii
Orice numă r natural 𝑎>1 se p oate scrie in mod unic (abstracț ie facand ordinea
factorilor) sub forma de produs de factori primi.

Demonstraț ie:
1. Existenț a (inductiv)

9
Afirmația este evident adevarată pentru 𝑎=2 care este prim. Daca 𝑎>2 ,
presupunând că toate numerele din {2,3,…,𝑎} sunt produse de factori primi, avem
cazurile:
i) Dacă 𝑎+1 este prim, atunci este clar ca o descompunere a lui 𝑎+1 in factori
primi este chiar 𝑎+1.
ii) Dacă 𝑎+1 este compus, atunci 𝑎=𝑏∙𝑐, unde 𝑏,𝑐≥2.
Conform ipotezei , 𝑏,𝑐 sunt evident mai mici decâ t 𝑎 și astfel sunt pr oduse de factori
ireductibili. În consecință, ș i 𝑎 are respectiva proprietate.
2. Unicitatea
Presupunem că există un numar natural care are mai multe scrieri de forma “produs de
factori ireductibili” . Notă m cu 𝑎0 cel mai mic dintre aceste numere.
Fie 𝑝1𝑝2∙…∙𝑝𝑟=𝑎0=𝑞1𝑞2∙…∙𝑞𝑠 doua scrieri ale lui a ca produs de factori
ireductibili.
Fixam 𝑝1≤⋯≤𝑝𝑟,𝑞1≤⋯≤𝑞𝑠.
Daca exista 𝑖,𝑗∈ℕ astfel incat 𝑝𝑖=𝑞𝑗, atunci
𝑝1∙…∙𝑝𝑖−1∙𝑝𝑖+1∙…∙𝑝𝑟=𝑞1∙…∙𝑞𝑗−1∙𝑞𝑗+1∙…∙𝑞𝑠<𝑎0
Observam ca scrierea trebuie sa fie total diferita. Prin urmare, vrem sa vedem daca un
factor din stanga este diferit de un factor din dreapt a. Pentru a ne fixa ideile, presupunem ca 𝑝1<
𝑞1.
Notam 𝑏=𝑝1𝑞2∙…∙𝑞𝑠<𝑞1∙…∙𝑞𝑠=𝑎0 (evident, deoarece 𝑝1<𝑞1).
Din propozitia (1.1.2) avem ca 𝑝1|𝑎0−𝑏.
𝑎0−𝑏=𝑞1∙…∙𝑞𝑠−𝑝1𝑞2∙…∙𝑞𝑠=𝑞2∙…∙𝑞𝑠(𝑞1−𝑝1)
Deci 𝑝1|𝑎0−𝑏=𝑞2∙…∙𝑞𝑠(𝑞1−𝑝1)<𝑎0.
Prin urmare, exista 𝑡1,…,𝑡𝑛 factori primi astfel incat
𝑝1𝑡2∙…∙𝑡𝑛=𝑎0−𝑏=(𝑞1−𝑝1)𝑞2∙…∙𝑞𝑠
Dar, 𝑞1−𝑝1 are si el o descompunere de forma 𝑞1−𝑝1=𝑤1∙…∙𝑤𝑘.
Cum 𝑝1∉{𝑤1,…,𝑤𝑘,𝑞2,…,𝑞𝑠}, cele doua scrieri ale lui 𝑎0−𝑏 ca produs de factori
primi sunt diferite , ceea ce ne conduce la o contradictie cu ipoteza.
În concluzie, niciun numar natural nu admite mai mult de o scriere sub formă de produs
de factori primi.
⧠

10
Teorema fundamentală a aritmeticii este un rezultat deosebit in domeniul criptografiei.
Acesta ne asigură de faptul ca există o factorizare pentru orice numă r natural. Factorizarea pentru
numere mici este destul de simplu de realizat, însa, cu cat numerele sunt mai mari, cu atat apar
probleme in gă sirea descompunerii.

1.2. Teste de primalitate
Modalitățile de a testa primalitatea unui număr 𝑛∈ℕ a fost și este un subiect extrem de
interesant in domeniul teoriei numerelor. Preocuparea oamenilor de știință pentru acest domeniu
este strâns legată de algoritmi puternici de criptare care se bazează pe lacune in domeniul analizei
numerelor prime și imp licit a factorizării numerelor prime.
Pornind de la celebrul algoritm pentru determinarea numerelor prime realizat de
matematicianul grec Erat ostene, stiinta a incercat sa găsească noi soluții pentru validarea
primalității unui numă r.
O metoda absolut tri vială de a testa dacă un număr 𝑛∈ℕ este prim este dată de următorul
algoritm :
𝑓𝑜𝑟 (i=2;i<n;i++)
𝑖𝑓 (n%i==0)
𝑟𝑒𝑡𝑢𝑟𝑛 𝑓𝑎𝑙𝑠𝑒 ;
𝑟𝑒𝑡𝑢𝑟𝑛 𝑡𝑟𝑢𝑒 ;
O îmbunătățire a algoritmului de mai sus se realizează astfel:
𝑓𝑜𝑟 (i=2;i<sqrt(n );i++)
𝑖𝑓 (n%i==0)
𝑟𝑒𝑡𝑢𝑟𝑛 𝑓𝑎𝑙𝑠𝑒 ;
𝑟𝑒𝑡𝑢𝑟𝑛 𝑡𝑟𝑢𝑒 ;

În general, ne interesează verific area primalității unui numă r de cat mai multe cifre. Aceste
numere prime mari au un rol foarte important in criptografie (1.3.1,1.3.2,1.3.3).
În acest capitol prezentam pe scurt principalele teste de primalitate, incepand de la cele mai
primitive, pană la testele folosite astăzi. Considerăm cunoscute noțiunile legate de aritmetică
modulară .

1.2.1 Teorema lui Wilson
Un numă r natural 𝑛>1 este pr im daca si numai daca (𝑛−1)!=−1 (𝑚𝑜𝑑 𝑛).

11
Demonstratie:
Pentru început consideră m polinomul 𝑓=𝑋𝑛−1−1∈ℤ𝑛[𝑋]. Din mica teoremă a lui
Fermat avem certitudinea că orice 𝑎∈ℤ𝑛\ {0} este rădăcină pentru polinomul 𝑓. Cum 𝑜𝑟𝑑(ℤ𝑛\
{0} )=| ℤ𝑛\ {0}|= 𝜑(𝑛)=𝑛−1=𝑔𝑟𝑎𝑑 (𝑓) si ℤ𝑛 este corp deoarece 𝑛 este prim, rădă cinile lui 𝑓
sunt 1,2,3…,n -1.
Conform relațiilor lui Viete și ț inand cont de faptul ca daca n este prim atunci n -1 sigur
este par, 1∙2∙3…∙(𝑛−1)=(𝑛−1)!=(−1)𝑛−1∙−1
1=−1, ceea ce încheie demonstraț ia.
⧠
Remarcăm faptul că aceasta teoremă are un caracter pur teoretic. Î n practica, este dific il
de implementat din cauza numărului mare de operaț ii pe care calculatorul este nevoit s ă le facă .

1.2.2 Teorema lui Euler
Dacă 𝑎∈ℤ, 𝑛∈ℕ, (𝑎,𝑛)=1 atunci 𝑎𝜑(𝑛)=1 𝑚𝑜𝑑 𝑛, unde prin 𝜑(𝑛) intelegem
indicatorul lui Euler , 𝜑(𝑛)=𝑐𝑎𝑟𝑑 {𝑥∈ℕ∩[1,𝑛−1]|gcd(𝑥,𝑛)=1}.
Demontrație :
Fie 𝑎∈ℤ, 𝑛∈ℕ, 𝑛 𝑝𝑟𝑖𝑚 , (𝑎,𝑛)=1. Atunci 𝑎∈𝑈(ℤ𝑛) fiind un element inversabil,
considerăm 𝑘=𝑜𝑟𝑑(𝑎). Stim ca 𝜑(𝑛)=𝑜𝑟𝑑(𝑈(ℤ𝑛) ) și din teorema lui Lagrange avem că
𝑘|𝜑(𝑛) deoarece ordinul oricărui element divide ordinul grupului.
Ca atare, există 𝑝∈ℤ a.i. 𝑘𝑝=𝜑(𝑛) si obținem 𝑎𝜑(𝑛)=𝑎𝑘𝑝=(𝑎𝑘)𝑝=1𝑝=
1 𝑚𝑜𝑑 𝑛.
⧠

1.2.3 Testul Fermat . Mincinosii Fermat. Numere Carmichael
Mica teorema a lui Fermat
Dacă 𝑝∈ℕ este prim, 𝑎∈[1,𝑝−1]∩ℤ , atunci 𝑎𝑝−1=1 𝑚𝑜𝑑 𝑝.
Demonstrație :
Considerăm 𝑝∈ℕ prim și 𝑎∈[1,𝑝−1]∩ℤ ales arbitrar. Deoarece 𝑝 este prim,
avem gcd(𝑎,𝑝)=1, așadar putem aplica teorema lui Euler ( 1.2.1).
Obținem 𝑎𝜑(𝑝)=𝑎𝑝−1=1 𝑚𝑜𝑑 𝑝, ceea ce incheie demonstrația.
⧠
Utilizând mica teoremă a lui Fermat, obținem un nou test de primalitate care nu este atât
de eficient și care pune destul de multe probl eme.

12
In cele ce urmează, urmărim să analizăm comportamentul testului Fermat în diferite
situații și să căutăm anumite proprietati ale numerelor Carmichael utilizand acest test.
Analizând mica teoremă a lui Fermat putem obține la prima vedere un criteriu
(test) de neprimalitate pentru un număr. Prin urmare, dacă dorim să verificăm primalitatea
unui număr natural 𝑛 și găsim un element 𝑐∈[1,𝑛−1]∩ℤ astfel încât 𝑐𝑛−1≠
1 𝑚𝑜𝑑 𝑛 , atunci cu certitudine acel număr 𝑝 nu este prim.
O să numim acest element 𝑐 validator al compunerii numărului 𝑛∈ℕ. Mulțimea
validatorilor compunerii unui număr natural 𝑛 o notăm cu 𝜔(𝑛).
𝜔(𝑛)={𝑐∈[1,𝑛−1]∩ℤ|𝑐𝑛−1≠1 𝑚𝑜𝑑 𝑛 }
De exemplu 4∈𝜔(9), deoarece 48=65536 =7 𝑚𝑜𝑑 9.
Din considerente practice, ne interesează testarea unui număr 𝑛∈ℕ,
𝑛>2,𝑛 𝑖𝑚𝑝𝑎𝑟 .

Propoziție 2.3 (Testul Fermat de primalitate)
Un număr 𝑛∈ℕ,𝑛>2 este prim dacă si numai dacă 𝜔(𝑛)=∅.
Demonstrație
=>
Daca 𝑛∈ℕ este prim , din mica teoremă a lui Fermat rezultă că
∀𝑎∈[1,𝑛−1]∩ℤ , atunci 𝑎𝑛−1=1 𝑚𝑜𝑑 𝑛, deci 𝜔(𝑛)=∅.
<=
Dacă 𝜔(𝑛)=∅ , presupunem prin reducere la absurd că 𝑛∈ℕ este compus ceea
ce ne conduce la o contradicție deoarece nu am avea validatori pentru compunerea
numarului 𝑛.
Notam in continuare 𝜇(𝑛)={𝑎∈[1,𝑛−1]∩ℤ|𝑎𝑛−1=1 𝑚𝑜𝑑 𝑛 }.
Propoziția 2.3 devine echivalentă cu faptul că un numar este prim dacă și numai
dacă 𝑐𝑎𝑟𝑑 (𝜇(𝑛))=𝑛−1.
Condiția 𝑐𝑎𝑟𝑑 (𝜇(𝑛))=𝑛−1 este absolut esențială, deoarece dacă ne uităm l a
numărul 869 , avem 1868=78868=791868=868868=1 𝑚𝑜𝑑 869 , însă
869 =11∙79 este un număr compus.
În exemplul anterior observă m că numerele 1,78,791 ,868 ∈𝜇(869 ) ne ofera o
informație mincinoasă legată de primalitatea numărului 869 . Interesant este de observat
cam cât de des apar aceste numere « mincinoase » atunci câ nd avem de a face cu un

13
număr compus și care este probabilitatea sa alegem un numar din mulțimea 𝜇 atunci când
testăm un număr care nu este prim.
Prin diferite procede e a fost arătat faptul că pentru o foarte mare parte din
numere, probabilitatea să alegem un număr din mulțimea 𝜇 și numă rul sa fie compus este
destul de mică, câteva verificări cresc foarte mult rata de siguranță a testului Fermat.
Există o « mică » par te a numerelor care infirmă cele spuse anterior.
Un exemplu de astfel de situație apare atunci când numărul 𝑛∈ℕ este compus, însa 𝑥∈
𝜇(𝑛),∀ 𝑥∈ℕ ,(𝑥,𝑛)=1 . Astfel de numere se numesc numere Carmichael.
Cel mai mic număr Carmichael este 561= 3∙11∙17. Aceste numere sunt foarte rare, însa
afecteaza foarte mult probabilitatea de succes a testului Fermat.
Tabel privind cele mai mici numere Carmichael în funcție de numărul de factori primi
care intră în descompunerea lor (http://www.chalcedon.demon.co.uk/ rgep/cartable.html) :

Așa cum spuneam, numerele Carmichael au făcut din testul Fermat o modalitate destul de
riscantă de a verifica primalitatea numerelor. Apariția algoritmului Miller -Rabin a incercat să
rezolve aceasta problemă.

14
Mai multe detalii privi nd numerele Carmichael regasim in capitolul 3 al acestei lucră ri.

Observaț ie:
În prezent, se reg ăsesc algoritmi mult mai eficienti de testare a primalității unui numă r (
de exemplu Miller -Rabil). In referitele bibliografice se regasesc lucrări care prezintă detaliat
acești algoritmi.

1.3. Rolul numerelor prime î n criptografie (problema factorizării si a
logaritmului discret)
În cele ce urmează, urmărim să prezentă m cele mai importante locuri in care apar
nume rele prime in criptografie. Accentul se pune pe analizarea celor doua probleme
fundamentale ale aritmeticii : problema factorizării ș i problema logaritmului discret. Fiecare
algoritm prezentat, vine impreun ă cu exemple pentru î ntelegerea procesului.

1.3.1. Problema factoriză rii si algoritmul RSA

Problema factorizării este una foarte simplă : se dă un număr compus N ș i se cere
descompunerea acestuia î n factori primi. In cazul unui numă r N de dimen siuni mici putem realiza
această descompunere manual fa ră prea mari dificultați, însă ce ne facem atunci c ând numă rul N
este de o dimensiune foarte mare?
Pornind de la această întrebare, î n anul 1977 Ron Rivest (R), Adi Shamir (S) si Leonard
Adleman (A) au propus un algoritm criptografic cu chei publice (RS A) tocmai bazându -se pe
această problemă dificil de rezolvat.

Principiul algoritmului se bazează pe alegerea a doua numere prime foarte mari p si q si
construirea numărului n=pq. Obținem așadar, un numă r compus care are drept divizori netriviali
numere le p si q. Deoarece 𝑝 si 𝑞 sunt numere prime , avem 𝜑(𝑛)=(p-1)(q-1).
Alegem un exponent de criptare e astfel î ncat gcd(𝑒,𝜑(𝑛))=1. Perechea rezultată
(n,e) reprezintă cheia publică .
Deoarece gcd(𝑒,𝜑(𝑛))=1 avem certitudinea că există un element 𝑑 astfel încâ t 𝑑𝑒=1

15
mod 𝜑(𝑛). Ca atare, 𝑑=𝑒−1 𝑚𝑜𝑑 𝜑(𝑛) exponent de descifrare.
Dacă vrem s a transmitem mesajul M , calculă m 𝑀𝑒 𝑚𝑜𝑑 𝑛 si trimitem 𝑀𝑒=𝐶., unde e
este cheia publica a destinatarului. Criptez cu cheia lui publica.
Cel care receptionează C decriptează mesajul ridicâ ndu-l la exponentul de descifrare d
(poate sa -l calculeze usor deoarece cunoaste 𝜑(𝑛) pentru n ales de el) .
𝐶𝑑=𝑀.

Justifica rea faptului că 𝐶𝑑=𝑀
𝐶𝑑=𝑀𝑒𝑑 𝑚𝑜𝑑 𝑛=𝑀𝑒𝑑𝑚𝑜𝑑 𝑛
Deoarece 𝑒𝑑=1 𝑚𝑜𝑑 𝜑(𝑛) => 𝑒𝑑−1=0 𝑚𝑜𝑑 𝜑(𝑛) , deci 𝜑(𝑛)|𝑒𝑑−1 .
Prin urmare , există 𝑘 numar întreg astfel î ncat 𝜑(𝑛)𝑘=𝑒𝑑−1 ,𝑑𝑒𝑐𝑖 𝑒𝑑=𝜑(𝑛)𝑘+1.
Obținem 𝑀𝑒𝑑=𝑀𝜑(𝑛)𝑘+1=(𝑀𝑘)𝜑(𝑛)𝑀 𝑚𝑜𝑑 𝑛=𝑀 deoarece (𝑀𝑘)𝜑(𝑛)=1 din
teorema lui Euler.

http://courses.cs.vt.edu/~cs5204/fall99/protection/publicKey.html

Avantajul celui care transmite mesajul este legat de faptul că poate calcula foarte uș or
valoarea indicatorului lui Euler pentru nu marul n ales deoacere îi cunoaște descompunerea î n
facto ri primi. Prin urmare, atunci când avem de a face cu un numă r foarte mare n care are doar
doi factori primi netriv iali, factorizarea sa reprezintă o problema chiar ș i pentru calculatoarele de
ultimă generație. O soluție la această problemă o poate reprezenta trecerea la calculatoar ele
cuantice, subiect analizat î n capitolul al treilea.

16

1.3.2 Problema logaritmului discret si protocolul Diffie -Helmann

Să presupunem că avem urmatoarea ecuaț ie exponentială în mulțimea numerelor î ntregi
𝑔𝑎=𝑦 𝑚𝑜𝑑 𝑝 , unde necunoscuta este 𝑎.
Definim drept soluție a acestei ecuaț ii , logaritmul discret 𝑎=log 𝑔𝑦 mod n.
În practică, atunci cand cunoaș tem g,y, si p este foarte dificil să găsim valoarea lui a atunci
când lucrăm cu numere mari. Această situație poartă numele de “problema logaritmului discret”.
Un exemplu in practică este oferit de catre protocolul de schimb de chei Diffie -Hellman.
Princ ipiul acestui protocol este urmă torul : Alice si Bob aleg de la bun î nceput un ℤ𝑝 , cu p
prim ș i 𝑔 un generator pentru grupul ( ℤ𝑝,∙).
Alice iș i alege cheia privat ă a, iar Bob alege cheia privată b.
Alice calculează 𝑔𝑎𝑚𝑜𝑑 𝑝 si îi trimite lui Bob ac est rezultat, iar Bob calculează 𝑔𝑏 𝑚𝑜𝑑 𝑝
si ii trimite lui Alice rezultatul obț inut.
Bob cunoaș te valoarea lui 𝑔𝑎 𝑚𝑜𝑑 𝑝, știe cine este 𝑔 si p, însă nu poate pune mâ na efectiv
pe 𝑎 tocmai din cauza problemei descrise anterior.
Alice calculează (𝑔𝑏)𝑎 𝑚𝑜𝑑 𝑝 si Bob calculează (𝑔𝑎)𝑏𝑚𝑜𝑑 𝑝 rezultâ nd cheia comuna.

Exemplu concret:
𝑝=17 ,𝑔=4 ,𝑎=13,𝑏=6;
Remarcăm faptul că <𝑔> =<4> ={40,41,…,}=ℤ17;
Alice →413𝑚𝑜𝑑 17=4 ; Bob →46𝑚𝑜𝑑 17=16;
Alice →1613𝑚𝑜𝑑 17=16=46𝑚𝑜𝑑 17← Bob .

Exemplificarea acestui procedeu este realizată pe pagina imediat următoare.

17

Exemplificarea protocolului Diffie -Hellman

18

CAPITOLUL II
Testul Fermat , numere Carmichael și algoritmul El Gamal
Studiul primalității unui numă r este un subiect extrem de important în teoria numerelor
avaâd numeroase aplicaț ii in criptografie.
În acest capitol, analizăm comportamentul mulț imii elementelor inversabile din ℤ𝑛 pentru
a vedea dacă această mulțime ne poate ajuta î n determinarea primalității unui numă r natural.
Principala motivație este de a căuta noi înformații în vederea unei posibil e optimiză ri a
testului Fermat si observarea anumitor propriet ăți.

2.1. Testul Fermat si analiza numerelor Carmichael
Observaț ii legate de elementele lui 𝐔(ℤ𝐧) . Funcț ia 𝛁𝛗(𝐧).

Fie 𝑛∈ℕ, si 𝑈(ℤ𝑛)={1=𝑢1,𝑢2,…,𝑢𝑘} , deci 𝜑(𝑛)=𝑘.

Numim secvență specială 𝛿𝑛 a lui 𝑈(ℤ𝑛) , orice secvență de termeni consecutivi de forma
𝛿𝑛∶ 𝑢𝑖,𝑢𝑖+1,…,𝑢𝑗 , 𝑖<𝑗 , unde 𝑢𝑘∈𝑈(ℤ𝑛) ∀𝑘∈[𝑖,𝑗]∩ℕ.
Mulțimea secvențelor speciale o notă m cu 𝑆𝛿.
Definim lungimea secvenț ei 𝛿𝑛 ca fiind 𝑙(𝛿𝑛)=𝑙(𝑢𝑖,𝑢𝑖+1,…,𝑢𝑗)=𝑢𝑗−𝑢𝑖+1 .

Exemplu:
Dacă 𝛿∶4,5,6,7,8 , atunci 𝑙(𝛿)=8−4+1=5

Pentru un numă r 𝑛∈ℕ oarecare , considerăm funcț ia ∇𝜑:ℕ→ℕ,
∇𝜑(𝑛)=max
𝛿𝑛∈𝑆𝛿𝑙(𝛿𝑛)

Aplicaț ie:
Calculati ∇𝜑(18).
Un prim pas este sa scriem mulț imea
𝑈(ℤ21)={1,2,4,5,8,10,11,13,16,17,19,20}.

19
𝑆𝛿={(1,2),(4,5),(10,11),(16,17),(19,20)}
Ca atare,
∇𝜑(18)=2
Propoziț ie 1
Dacă 𝑝∈ℕ este prim , atunci ∇𝜑(𝑝)=𝜑(𝑝)=𝑝−1.
Demonstraț ie:
Fie 𝑝∈ℕ,𝑝 prim. Evident, 𝑈(ℤ𝑝)={1,2,3,…,𝑝−1} , deci 𝑆𝛿={(𝑈(ℤ𝑝))}.
Ca atare, ∇𝜑(18)=𝑙(1,2,3,…,𝑝−1)=𝑝−1−1+1=𝑝−1.

2.1.2 Analiză asupra funcț iei 𝛁𝝋(𝒏)

În teoria numerelor, atunci când avem de a face cu o funcție aritmetică, o
importanță deosebită este realizarea graficului unei astfel de funcț ii , to cmai pentru a
studia o eventuală tendință a valorilor sale.

Ne propunem să analizăm comportamentul funcț iei ∇𝜑(𝑛) pentru
3≤𝑛≤𝑣𝑎𝑙𝑚𝑎𝑥 .

Propoziț ie 2.1
Dacă 𝑛∈ℕ este un numă r natural par atunci ∇𝜑(𝑛)=0.
Demonstraț ie:
Fie 𝑛∈ℕ un numă r par si 𝑈(ℤ𝑛)={1,𝑢2,…,𝑢𝑠} . Cum 𝑛 este impar , 𝑢𝑘≠𝑢𝑘+1 , altfel
am avea doi termeni consecutivi î n 𝑈(ℤ𝑛) de forma par -impar ceea ce ne -ar conduce la o
contradicț ie cu ipoteza.

Propoziț ie 2.2
Fie 𝑛∈ℕ 𝑖𝑚𝑝𝑎𝑟 , atunci ∇𝜑(𝑛)+1 este cel mai mic fac tor prim diferit de 1 c are intră în
descompunerea numă rului 𝑛.
Demonstraț ie:

20
Fie 𝑛∈ℕ un numă r impar si 𝑈(ℤ𝑛)={1,𝑢2,…,𝑢𝑠}. Este evident că orice n umar par mai
mic decat n se regăsește în mulț imea 𝑈(ℤ𝑛).
Deci, 𝑈(ℤ𝑛)={1,2,𝑢3,4,𝑢5,…,𝑛−1}. Secvența maximă de termeni consecutivi din
𝑈(ℤ𝑛) se oprește în momentul în care gasește primul numă r prim 𝑢𝑖 la care 𝑛 se împarte exact.

Morala este că ∇𝜑(𝑛) presupune verificarea pas cu pas a elementelor inversabile din
𝑈(ℤ𝑛) , echivalent cu a spune că dorim sa ca utăm cel mai mic fa ctor prim din descompunerea
numă rului 𝑛.
Simulâ nd cu ajutorul calcul atorului, descoperim faptul ca ș irul
𝑙(𝛿𝑛1),…, 𝑙(𝛿𝑛𝑐𝑎𝑟𝑑 (𝑆𝛿))
conține valoarea lui ∇𝜑(𝑛) de mai multe ori, așadar este interesant de urmă rit care este
probabilitatea ca alegând o secvență specială din mulț imea 𝑆𝛿𝑛 , aceasta să fie de lungimea
∇𝜑(𝑛), adică de lungime maximă .

2.1.3.Probab ilitatea determină rii 𝛁𝝋(𝒏) alegând la întamplare o secvență din
𝑺𝜹𝒏

Testul Fermat
Acest test de primalitate pleacă de la urmă torul rezultat, cuno scut sub numele de “Mica
teoremă a lui Fermat”:
Dacă 𝑝∈ℕ este prim, ∈[1,𝑝−1]∩ℤ , atunci 𝑎𝑝−1=1 𝑚𝑜𝑑 𝑝.

Cu alte cuvinte, dacă vrem să testăm primalitatea unui număr, în practică este suficient să
facem un număr relativ redus de verifică ri pentru 𝑎∈[1,𝑝−1]∩ℤ ca să afirmă m cu o
probabilitate mare ca acest număr este prim sau nu. Dacă gă sim un 𝑎∈[1,𝑝−1]∩ℤ astfel încâ t
𝑎𝑝−1≠1 𝑚𝑜𝑑 𝑝, atunci cu certitudine numă rul nu este prim.
Există î nsa numere 𝑛 care trec testul Fermat (i.e. sunt considerate prime) pentru orice
martor din multimea 𝑈(ℤ𝑛). Ace ste numere se numesc Carmichael , cel mai mic dintre ele fiind
561= 3∙11∙17. Numerele Carmichael sunt destul de rar întalnite, insă existenta lor afectează
foarte mult eficienț a testului Fermat.

21
Așa cum am văzut î n capitolul anterior, ∇𝜑(𝑛) reprezintă o unealtă utila din punct de
vedere teoretic pentru a verifica daca un numar este prim cu ajutorul testului Fermat, deoarece o
alegere a ∇𝜑(𝑛)+1 termeni consecutivi pentru a fi martori in testul Fermat, ar exclude
posibilitatea ca testul sa se înșele în privinț a numerelor Carmichael.
Partea mai putin placută este legată de modul în care testă m numerele Carmichael de
dimensiuni mari (multe cifre). Dacă în descompunerea numărului Carmichael se află un factor
prim mare, atunci calculul ∇𝜑(𝑛) este destul de incomod de realizat din s implul fapt că am avea
multe iteraț ii.
Ne punem următoarele doua întrebă ri:
1. Care este probabilitatea ca alegând o secvență specială în mod aleator din muț imea 𝑆𝛿
aceasta să fie de lungime maximă ?
2. Găsim o legatură între distribuț ia numerelor impare c ompuse si probabilitățile de a
găsi o secvență de lungime maximă alegând aleator o secvență din 𝑆𝛿.
Folosind calculatorul ș i determinând mulțimea secvențelor, secvența de lungime
maximă și probabilitatea ca o secvență să fie de lungime maximă , pentru numerele impa re
compuse de la 3 la 99 999 obținem urmă toarele rezultate:

40408 numere
22 cu probabilitatea <0.01
501 cu probabi litatea intre 0.1 si 0.10
4629 cu probabilitatea intre 0.10 si 0.5
4641 cu probabilitatea intre 0.5 si 0.8
4241 cu probabilitatea intre 0.8 si 0.95
26374 cu probabilitatea peste 0.95

Numerele Carmichael <99 999 și probabilitatea de a găsi secvența de lungime
maximă :
561 1
1105 0.53
1729 0.3
2465 0.66
2821 0.36

22
6601 0.56
8911 0.55
10585 0.81
15841 0.68
29341 0.4
41041 0.17
46657 0.46
52633 0.82
62745 1
63973 0.25
75361 0.03

Dacă analiză m cele 22 de numere la care secvența de lungime maximă este gasită cu o
probabilitate de sub 1% , observăm urmă toarele rezultate:

23

2.2. Algoritmul El Gamal pe curbe eliptice

Introducere
Obiective:
-construirea unei aplicații C++ bazată pe programare procedurală care să realizeze cifrarea El
Gamal pe curbe eliptice de ordin numă r prim
-implementarea noțiunii de rest pă tratic pentru a determina punctele de pe o curbă eliptica peste
un grup finit ℤ/𝑛ℤ
-generarea t uturor elementelor de pe o curbă eliptică de ordin numă r prim pornind de la un
element dat 𝛼
-codificarea unui mesaj folosind metoda El Gamal ș i elementele generate de 𝛼

24
Observaț ie:
Aplicaț ia are un caract er pur didactic si nu se bazează pe urmă rirea reducerii timpului de
execuție atunci când lucră m cu n umere foarte mari.
Structura algebrică de grup a curbelor eliptice

Este cunoscut faptul că o curbă eliptica 𝐸 peste ℤ/𝑛ℤ formează o structura de grup
abelian împreună cu adunare a punctelor de pe curba eliptică .
În cele ce urmează, elementul neutru de pe o curbă eliptică E(denumit in mod generic
“punctul de la infinit”)o sa fie considerat punctul ( -1,-1).
Fie acum o curbă eliptică E peste ℤ/𝑛ℤ si 𝛼∈E un punct de pe curba eliptică .
Mulț imea elementelor generate de 𝛼 se notează cu <𝛼> si este descrisă astfel:
<𝛼> ={𝛼,𝛼2,𝛼3,…,𝛼𝑘−1,(−1,−1)}
Reamintim , 𝛼𝑘=𝛼+𝛼+⋯+𝛼,𝑑𝑒 𝑘 𝑜𝑟𝑖=𝑘𝛼, unde prin “+” intelegem adunarea
punctelor de pe curba eliptica 𝐸, deoarece (E,+) este un grup abelian de tip aditiv.
Dacă avem un numă r prim de pun cte pe curba eliptica E, utilizâ nd teorema lui Lagrange
pentru grupuri avem că 𝑜𝑟𝑑(𝛼)=𝑘=𝑐𝑎𝑟𝑑 (𝐸)=𝑜𝑟𝑑(𝐸), cu alte cuvinte,
<𝛼>=E ,∀α∈E−{(−1,−1)}
Morala este că într -un grup finit de ordin număr prim, orice element generează î ntregul
grup.
Scurtă prezentare a cifră rii El Gamal
Fie (𝐸,+) un gru p finit constituit dintr -o curbă eliptică peste ℤ/𝑝ℤ, p prim.
Consideră m un element 𝛼∈𝐸 si subgrupul generat de 𝛼 unde problema lo garitmului
discret este dificilă. În cazul nostru, urmă rim curbele eliptice cu un numar prim de elemente, ca
atare o rice element o sa genereze î ntregul grup.
Alegem cheia privată 𝑑∈ℤ si calculă m 𝛽=𝑑𝛼.
Obținem cheia publică : {𝐸,𝛼,𝛽}.
Pentru a cifra mesajul 𝑀=(𝑚1,𝑚2), M ele ment(punct) de pe curba eliptică , se alege
aleatoriu 𝑘∈ℤ/𝑝ℤ si se aplica urmatoarea regula de cifrare:
𝑐𝑖𝑓𝑟𝑎𝑟𝑒 (𝑀,𝑘)=(𝑘𝛼,𝑀+𝑘𝛽)=(𝑦1,𝑦2)

25
Recuperarea mesajului clar:
𝑦2−𝑑𝑦1=𝑀+𝑘𝛽−𝑑𝑘𝛼 =𝑀+𝑘𝑑𝛼 −𝑑𝑘𝛼 =𝑀
Prezentarea aplicaț iei
OBSERVAȚ IE :
Fiecare comentariu este legat de liniile de program de deasupra lui.

#include <iostream>
//#include <fstream.h>
using namespace std;
long int reduceremodulara(long int q,long int w)
{//q redus modulo w
while (q<0)
q+=w;
return q;
}
Această funcție are rolul de a reduce un numă r negativ q modulo w.
long int modularinverse(long int a, long int n)
{long int i;
for (i=0;i<=n -1;i++)
if ((a*i)%n==1)
return i;
}
Această funcție returnează inversul modular al unui element a mod n. Modalitatea
este bazată pe forta bruta ( tabla î nmul țirii).
long int primetest(long int n)
{

26
long int i;
if(n==1)
return 0;
for (i=2;i<=n/2;i++)
if(n%i==0)
return 0;
return 1;
}
Această funcț ie este un test tr ivial pentru tastarea primalitații unui numă r n.

long int exprapida(long int p,long int k,long int n)
{long int i,q=1;

for (i=1;i<=k;i++)
{q=q*p;
q=q%n;}
return q;
}
Această funcție realizează exponențiala rapidă .
long int quadsqrt(long int a,long int prim)
{long int k,i;
if((prim -3)%4==0)
{k=(prim -3)/4;
return exprapida(a,k+1,prim);
}

27
for (i=0;i<=prim -1;i++)
if (exprapida(i,2,prim)==a)
return i;
}
Această funcție returnează soluția ecuaț iei 𝒙𝟐=𝒂 (𝒎𝒐𝒅 𝒏), atunci când a este
evident rest pă tratic modulo n.

long int xulsumei(long int x1,long int y1,long int x2,long int y2,long int n,long int
parametrula)
{long int x;
long int lambda;
if (x1==x2 && y1==y2)
lambda=(((3*x1*x1)+parametrula)*modularinverse(2*y1,n))%n;
else
lambda=(reduceremodulara((y2 -y1),n)*modularinverse(reduceremodulara(x2 –
x1,n),n))%n;
if (x1==x2 && y2==n -y1)
{x=-1;
return x;
}
else
{x=reduceremodulara((lambda*lambda -x1-x2),n)%n;
return x;
}
}
Această funcție returnează prima componentă a unei sume de doua puncte pe curba
eliptică .

28

long int yulsumei(long int x1,long int y1,long int x2,long int y2,long int n,long int
parametrula)
{long int y;
long int lambda;
if (x1==x2 && y1==y2)
lambda=(((3*x1*x1)+parametrula)*modularinverse(2*y1,n))%n;
else
lambda=(reduceremodulara((y2 -y1),n)*modularinverse(reduceremodulara(x2 –
x1,n),n))%n;
if (x1==x2 && y2==n -y1)
{y=-1;
return y;
}
else
{y=lambda*x1 -lambda*xulsumei(x1,y1,x2,y2,n,parametrula) -y1;
y=reduceremodulara(y,n)%n;
return y;
}
}
Aceasta functie returneaza a doua componenta a unei sume de doua puncte pe curba
eliptica.

struct coordonate {
long int x,y;
};

29
Aceasta este o structură prin care putem face referire mai uș or la coordonatele unui
punct.

int m ain()
{coordonate v[500],alpha,mesaj,table[500],beta;
În v salvă m punctele de pe E, alpha este generatorul ales, me saj este mesajul pe care
vrem să -l cifrăm, table reprezintă tabloul elementelor g enerate de alpha, iar beta intră î n
cifrarea El Gamal.
long int a,b,d,k,dimorde=0,p,i,z,coeficientmesaj;
cout<<"p:";cin>>p;
cout<<"Parametrul a:";cin>>a;
cout<<"Parametrul b:";cin>>b;
cout<<"Expresia analitica a curbei eliptice este:"<<"y^2=x^3+"<<a<<"x+"<<b<<endl;
Citirea lui p ș i a parametrilor curbei eliptice.
for (i=0;i<=p -1;i++)
{z=((i*i*i)+(a*i)+b)%p; //Află m valorile y^2 pentru fiecare x că utat
if(z==0) //Dacă y^2=0 , atunci sigur un punct de pe E este (x,0)
{
dimorde++;
v[dimorde].x=i;
v[dimorde].y=0;
}
if(exprapida(z,(p -1)/2,p)==1) //Testă m cu aj utorul formulei lui Euler daca z este
{//cout<<"uite i:"<<i; rest pă tratic modulo p
dimorde++;
v[dimorde].x=i;
v[dimorde].y=quadsqrt(z,p); //Calculăm soluțiile ecuaț iei y^2 =z;

30
dimorde++;
v[dimorde].x=i;
v[dimorde].y=p -quadsqrt(z,p);
}
}
cout<<"Punctele de pe curba eliptica sunt:"<<endl;
for (i=1;i<=dimorde;i++)
cout<<"("<<v[i].x<<","<<v[i].y<<")"<<endl;
cout<<"O"<<endl;
Am afișat punctele de pe curba eliptică .
if (primetest(dimorde+1)==0) // Ve rificăm dacă numărul de elemente de pe curba E
este un număr prim . Am adunat 1 deoarece ș i punctul de la infinit este mereu un element
de pe curba eliptică .
{
cout<<"Numarul punctelor de pe E este "<<dimorde+1<<",care nu este prim";
}
else
{
cout<<"Cum numarul punctelor de pe E este "<<dimorde+1<<", ordinul lui E este un
numar prim.";
cout<<endl<<"Prin urmare, orice element din E este generator al punctelor de pe E.";
cout<<endl<<"Tastati componenta x a generatorului dorit:";
cin>>alpha.x;
cout<<"Tastati componenta y a generatorului dorit:";
cin>>alpha.y;
table[1].x=alpha.x;table[1].y=alpha.y;
for (i=2;i<=dimorde+1;i++)

31
{
table[i].x=xulsumei(table[i -1].x,table[i -1].y,table[1].x,table[1].y,p,a);
table[i].y=yulsume i(table[i -1].x,table[i -1].y,table[1].x,table[1].y,p,a);
}
Realiză m tabelul elementelor generate de alpha.
cout<<"Punctele generate de elementul ales:"<<endl;
for (i=1;i<=dimorde+1;i++)
cout<<"("<<table[i].x<<","<<table[i].y<<")"<<endl;
cout<<endl;
Afișăm elementele generate de alpha.
cout<<"Tastati prima componenta a mesajului dorit:";
cin>>mesaj.x;
cout<<"Tastati a doua componenta a mesajului dorit:";
cin>>mesaj.y;
cout<<"Introduceti cheia privata d:";
cin>>d;
cout<<"Introduceti valoarea k:";
cin>>k;
beta.x=table[d].x;
beta.y=table[d].y;
cout<<"Cheia publica este urmatoarea:"<<endl;
cout<<"(("<<alpha.x<<","<<alpha.y<<"),("<<beta.x<<","<<beta.y<<"))";
Calculez și afișez cheia publică .
for (i=1;i<=dimorde+1;i++)
{
if (mesaj.x==table[i].x && mesaj.y== table[i].y) //mă î ntreb al catelea element

32
{coeficientmesaj=i; în tabloul generat de alpha este mesajul M
i=dimorde+2;}
}
long int coeficientcriptare;
coeficientcriptare=(coeficientmesaj+(d*k))%(dimorde+1);
cout<<endl<< "Mesajul criptat este urmatorul:"<<endl;
cout<<"(("<<table[k].x<<","<<table[k].y<<"),("<<table[coeficientcriptare].x<<","<<table
[coeficientcriptare].y<<"))";
}
Realizarea cifră rii El Gamal.
return 0;
}
1.3.3.5. Exemple
1. Fie 𝐸:𝑦2=𝑥3+𝑥+6 𝑚𝑜𝑑 13. Considerâ nd generatorul 𝛼=(4,3), cheia privată
𝑑=3, sa se cifreze mesajul 𝑀=(3,7) cu 𝑘=4.
Verificaț i prin descifrare.
Programul rulează această problemă astfel:

33

Observăm că obtinem m esajul criptat ((9,4),(2,9)). Să -l verificam prin descifrare!
((9,4),(2,9))=(y1,y2)
𝑦2−𝑑𝑦1=(2,9)−3(9,4)=2𝛼−3∙4𝛼=2𝛼−12𝛼=2𝛼+𝛼=3𝛼=(3,7)=𝑀.

2. Fie 𝐸:𝑦2=𝑥3+21𝑥+7 𝑚𝑜𝑑 13. Considerâ nd generatorul 𝛼=(7,4), cheia privat ă
𝑑=7, să se cifreze mesajul 𝑀=(11,3) cu 𝑘=8.
Verificaț i prin descifrare.

34
Programul rulează această problemă astfel:

Observăm ca obtinem m esajul criptat ((4,8),(4,5)). Să -l verificam prin descifrare!
((4,8),(4,5))=(y1,y2)
𝑦2−𝑑𝑦1=(4,5)−7(4,8)=3𝛼−7∙8𝛼=3𝛼−56𝛼=3𝛼−𝛼=3𝛼+10𝛼=13𝛼=2𝛼
=(11,3)=𝑀.

35
CAPITOLUL III
Criptarea cuantică

3.1 Noț iuni generale legate de criptarea cuantică
Punctul de plecare al criptării cuantice este strâ ns legat de principiul incertitudinii al lui
Heinseberg. Acesta afirmă că nu putem cunoaș te exact la un moment dat viteza și poziția unei
particule. Dacă privim lumina formată din particule de energie (fotoni) , atu nci câ nd privim la
microscop, un foton nu are un efect se mnificativ asupra unui obiect. În momentul în care ne
raportăm la o scară subatomică , fotonii loves c particula subatomică și influențează mișcarea
aceste ia. Prin urmare, măsurând poziț ia particule i, viteza acesteia s -a modificat. Apare așa zisa
problemă legată de faptul că “observarea afectează obiectul de observat”. Morala este că
rezultatul măsură torii unui sistem nu este determinist, ci descris de un mo del probabilist.
De exemplu, pentru a afla poziț ia unui electron, acesta trebuie să reflecte fotoni care la
rândul lor să loveas că de electron și să fie reflectați către dispozitiv. Î n cazul unei partic ule mari,
incertitudinea măsurării poziției este mică, însă î n cazul particulelor mici (subatomice)
incertitudinea este foarte mare.
Făcâ nd comparatie cu sistemele criptografice tradi ționale care se bazează pe metod e
matematice, criptarea cuantică are la princip iile fizicii cuantice. Atunci când interceptăm o
informaț ie, aces t proces poate fi privit ca o mă surare a un ui obiect fizic (cel care poartă
informația). Plecâ nd de la fenomen e cuantice (suprapunere cuantică și legătura cuantică ) putem
realiza un si stem criptografic care să fie imposibil de atacat. Mot ivul este acela că purtatorul
cuantic își modifică mereu proprietățile și eventualele interceptări afectează atacul î n sine.
Mai multe detalii legate de abordă ri ale acestei probleme se reg ăsesc î n lucrarea [10].
Revenind la p rincipalul scop al acestei lucrări, dorim să vedem unde apar numerele prime
în partea de criptare cuantică. Un calculator se numește cuantic dacă are la bază fenomenele
cuantice de superpoziție ș i inseparabili tate cuantică (entanglement). Aș adar, spre deos ebire de
calculatoarele clasice care funcționeaza pe bază de tranzistori, quantum computing este un
domeniu de viitor care ar asigura o rapiditate mai mare de procesare a informaț iei.

36
Legă tura/ insepar abilitatea cuantică este un fenomen î n car e stările cuantice ale mai multe
particule sunt cuplate î ntre ele. Ca atare, un obiect sepa rat nu mai poate fi descris fără a lua î n
considera re celelalte obiecte, chiar dacă ele sunt separate din punct de vedere spațial.
Un calculator cuantic funcțion ează pe baza fe nomenelor cuantice de superpoziție ș i
inseparabilitate. Spre deoesbire de calculatoarele clasice care folosesc bitul ca unitate
fundamentală de stocare a informaț iei, calculatoarele cuantice se bazează pe qubit (quantum bit) ,
care po ate fi 1 , 0 sau orice superpoziție cuantică a acestora. Acest lucru conduce la faptul că
putem efectua un număr mult mai mare de operații î ntr-un timp considerabil mai mic decât î n
cazul calculatoarelor clasice.
Calculatorul cuantic este implementat sub f orma unui sistem cuantic care posedă stări
independente și care este descris prin funcția de stare. Prin urmare, funcția de stare (denumită în
particular și funcșie de undă) descrie o stare dinamică a unui sistem atomic. La baza acestui
concept se află pri ncipiul superpoziției, funcț iile de stare devenind elemente ale unui spaț iu
vectorial. Pentru a implementa funcț ia de st are trebuie ca vectorii din spațiul vectorial al stărilor
să fie caracterizați prin mărime ș i orientare. Definind un produs scalar, spațiul stărilor devine un
spațiu prehilbertian.
Principiul superpoziției (suprapunerii) afirmă faptul că î n oricare sistem liniar rasp unsul
generat la un moment dat și la o anumită poziție de că tre mai mulți stimuli este egal cu suma
răspunsuri lor generate de fiecare stimul î n parte.
În mecanica clasică, dacă mai multe forțe acționează simultan asupra unui corp, fiecare
forță produce propria sa accelerație în mod independent de prezența celorlalte forțe. Pri n urmare,
accelerația rezultantă este suma vectoriala a acceleraț iilor individuale.
În mecanica cuantică, dacă avem un sistem cuantic descris de funcț iile de unda 𝜑𝑖 ,𝑖∈
{1,2,…𝑛} in starile cuantice 𝑖∈{1,2,…𝑛} atunci o posibilă stare a sistemului este caracterizată
de funcț ia 𝜑=∑𝑎𝑖𝜑𝑖 , unde 𝑎𝑖 sunt amplitudinile funcțiilor de undă .
În cele ce urmează, prezentăm o exemplificare a factorizării unui numă r compus (format
din produsul a două numere prime) folosind algo ritmul lui Shor care are la bază calculatoarele
cuantice.

37
Pentru m ai multe detalii privind modul în care lucrează acest algoritm, se recomandă
studierea materialelor din biblio grafie care fac referire la conț inutul articolului de mai jos.
3.2 Un nou exemplu de factorizare a unui î ntreg folosind algoritmul lui Shor

Peter Shor
În acest articol urmărim să tratăm problema factoriză rii numerelor pe calculatoare
cuantice. Principalul scop este acela de a prezenta algoritmul Shor î ntr-o nou ă abordare care se
axează pe exemplificare concretă urma rind ideile principale din [1], [2] și [4].

Etape:

1. Problema factorizării pe calculatoare cuantice ;
2. Algoritmul lui Shor. Analiza pe baza unui exemplu.

1. PROBLEMA FACTORIZĂ RII PE CALCULATOARE CUANTICE

Factorizarea unui număr î ntreg foarte mare este o problemă foarte importantă în
domeniul criptografiei. De exemplu, algoritmul RSA are la bază această incapacitate a
calculatoarelor de a factoriza numere cu fo arte multe cifre. Ca o consecință, au apă rut alg oritmi
care realizează factorizarea pe calculatoarele clasice, însă numerele cu foarte multe cifre pun
probleme acestor algoritmi din punctul de vedere al timpului de execuț ie. Pentru mai multe
detalii puteț i consulta [1].
O soluție pentru această problemă referitoare la timpul de execuție atunci când dorim să
factorizăm un număr foarte mare a fost propusă de către matematicianul Peter Shor î n anul
1994 [7]. Algoritmul propus de către Shor necesită la unul dintre paș i un calculator cuantic

38
pentru a realiza anu mite operaț ii matematice.

2. EXEMPLIFICAREA ALGORITMULUI LUI SHOR
În continuare, prezentăm un articol realizat de către autorul acestei lucrari în care se
prezintă o nouă exemplificare a algoritmului lui Shor.
În cele ce urmează dorim să exemplifică m mod ul în care algoritmul Shor găsește
factorizarea unui număr întreg foarte mare. O primă observație legată de acest algoritm este că la
un singur pas necesită un calculator cuantic.
Pentru a factoriza un numă r 𝑛∈ℕ este cunoscut faptul că este suficient să găsim un
numă r 𝑚∈ℕ relativ prim cu n și să caut cel mai mic numă r 𝑘∈ℕ∗ astfel încâ t
𝑚𝑘=1 𝑚𝑜𝑑 𝑛.
Ideea pe care se bazează acest algoritm este aceea de a găsi perioada următoarei funcț ii:
𝑓(𝑥)=𝑚𝑥 𝑚𝑜𝑑 𝑛
Etapele și demonstraț iile detal iate se găsesc în lucră rile [1], [2], [5] și [7 ]. Ne interesează
o exemplificare a acestor noțiuni pentru a înțelege concret cum funcționează acest algoritm.
Ne propunem sa gasim factorizarea numarului 143 =11∙13. Din motive tehnice am ales
un numar relativ mic.
La un p rim pas , alegem la întâmplare un număr î ntreg 𝑚 si calculă m cu ajutorul
algoritmului lui Euclid gcd(m,143). Dac ă avem norocul ca gcd (𝑚,143 )≠1 atunci problema
este rezolvată deoarece am gă sit un factor netriv ial din descompunerea lui 143. Î n cazul in care
gcd(𝑚,143 )=1 ( sa ne fixă m m= 5) ,atunci alegem un î ntreg 𝑊=2𝑡 care sa respecte condiț ia
1432≤𝑊<2∙1432 (de exemplu 𝑊=215=32768 ) și trecem la pasul al doilea.
Pasul al doilea este cel mai important din algoritmu l lui Shor. Aici este nece sar să
determină m cu ajutorul unui c alculator cuantic perioada funcț iei 𝑓(𝑥)=5𝑥 𝑚𝑜𝑑 143.
Calculând, obținem urmă toarele valori: 51≡5 ,52≡25, 53≡125 ,54≡53,55≡
122 ,56≡38,57≡47,58≡92,59≡21,510≡12,511≡60,512≡14,513≡70,514≡

39
64,515≡34,516≡27,517≡135 ,518≡103 ,519≡86,520≡1 … ceea ce ne conduce la faptul
că perio ada acestei funcț ii este 𝑝=20.
Construm cei doi registrii cuantici [5 ] după care îi inițializă m cu valorile 0 astfel:
|𝛹0>=|00…>|00…>
Aplicâ nd transformata Fourier primului regist ru, siste mul cuantic se modifică astfel:
|𝛹1>=1
√32768∑ |𝑥>|0>32767
𝑥=0
Pentru a modifica și al doilea registru, aplică m transformata 𝐻𝑓 unitară (Fou rier sau
Hadamard) ambilor regiștrii si obș inem:
𝑈𝑓(|𝑥>|0>)=1
√32768∑ |𝑥>|5𝑥𝑚𝑜𝑑 143 >32767
𝑥=0=
=1
√32768(|0>|1>+|1>|5>+⋯+|19>|86>+|20>|1>+⋯+|32767
>|51638 ∙20+7=(520)1638∙57=1∙57≡47>)
În acest moment avem o incarcatură cuantică privind cei doi regiștrii, nu doar superpoziț ii
de stare.
Cum 𝑈𝑓 este un op erator liniar, acesta actionează în paralel asupra tuturor stărilor |𝑥>
|0> pentru toate cele 32768 valori ale lui 𝑥. Această proprietate este cunoscută sub numele de
paralelism cuantic.
Aplicâ nd din nou transformata Fourier registrului de pe prima pozitie (procedeu explicat
in [1]) , starea sistemului nostru dev ine:
|𝛹3> =1
√32768∑1
√3276832767
𝑥=0∑ 𝜇𝑥𝑦|𝑦>|5𝑥𝑚𝑜𝑑 143 >32767
𝑦=0=
=1
32768∑ |𝑦>∑ 𝜇𝑥𝑦|5𝑥𝑚𝑜𝑑 143 >32767
𝑥=0=1
32768∑ |𝑦>|𝜃(𝑦)>32767
𝑦=032767
𝑦=0

40

unde,
𝜇=𝑒2𝜋𝑖
32768
iar ,
|𝜃(𝑦)> =∑ 𝜇𝑥𝑦|5𝑥𝑚𝑜𝑑 143 >32767
𝑥=0
Prin urmare ,
|𝜃(𝑦)> =|1>+𝜇𝑦|5>+𝜇2𝑦|25>+⋯+𝜇20𝑦|1>+⋯+𝜇32767 𝑦|47>
Deoarece funcț ia 5𝑥=1 𝑚𝑜𝑑 143 este periodică , putem masura primul parametru
pentru un 𝑘 oarecare probabilitatea ca 𝑘=𝑘0→|𝑦>|𝑓(𝑘0)> [1].
Orice ieș ire 50,51,…,520−1 poate fi obținută cu aceeaș i probabilitate.
Să presupunem că în urma măsurătorii , am obț inut parametrul 𝑦=31117 . Calculâ nd
𝑑(𝑦)=𝑝
𝑊∙31117 =622340
32768≈18.99 si rotunjind la cel mai apropiat întreg obț inem
𝑑(𝑦)=19.
Pentru a putea continua algoritmul este necesar ca gcd(𝑑(𝑦),𝑝=20)=1. Această
probabili tate este destul de mica [5 ] , însă suntem norocoși ș i putem merge mai departe.
Cunoastem că 𝑑(𝑦)
𝑝 este limita fracț iei continue 𝜉=𝑦
𝑊=31117
32768 [5].
𝜉=𝑦
𝑊=31117
32768=0+1
32768
31117=0+1
1+1651
31117=0+1
1+1
31117
1651=0+1
1+1
18+1399
1651=

41
=0+1
1+1
18+1
1651
1399=0+1
1+1
18+1
1+252
1399=0+1
1+1
18+1
1+1
1399
252
=0+1
1+1
18+1
1+1
5+139
252
=0+1
1+1
18+1
1+1
5+1
252
139=0+1
1+1
18+1
1+1
5+1
1+113
139=0+1
1+1
18+1
1+1
5+1
1+1
139
113
=0+1
1+1
18+1
1+1
5+1
1+1
1+26
113=0+1
1+1
18+1
1+1
5+1
1+1
1+1
113
26
=0+1
1+1
18+1
1+1
5+1
1+1
1+1
4+9
26=0+1
1+1
18+1
1+1
5+1
1+1
1+1
4+1
26
9
=0+1
1+1
18+1
1+1
5+1
1+1
1+1
4+1
2+8
9=0+1
1+1
18+1
1+1
5+1
1+1
1+1
4+1
2+1
9
8

42
0+1
1+1
18+1
1+1
5+1
1+1
1+1
4+1
2+1
1+1
8
Așadar, 𝜉=[0,1,18,1,5,1,1,4,2,1,8]

Bazându -ne pe urmă toarele formule [5 ] ,
𝜉𝑛=𝑝𝑛
𝑞𝑛,𝑝0=0 ,𝑞0=1,𝑝1=𝑎1𝑎0+1 ,𝑞1=𝑎1
{𝑝𝑛=𝑎𝑛𝑝𝑛−1+𝑝𝑛−2
𝑞𝑛=𝑎𝑛𝑞𝑛−1+𝑞𝑛−2
obținem:
𝑝1=𝑎1𝑎0+1=1
𝑞1=1
𝑝2=𝑎2𝑝1+𝑝0=18∙1+0=18
𝑞2=𝑎2𝑞1+𝑞0=18∙1+1=19
Testă m 𝑞2=8 . Avem 5𝑞2=519=86 𝑚𝑜𝑑 143 ceea ce nu ne convine din cauza
faptului că dorim să obținem 1. Continuă m calculele:
𝑞3=𝑎3𝑞2+𝑞1=1∙19+1=20
Cum 5𝑞3=520=1 𝑚𝑜𝑑 143 acest pas se încheie deoarece am obținut perioada funcț iei
𝑓(𝑥)=5𝑥 𝑚𝑜𝑑 143.

43

https://www.researchgate.net/figure/High -level -diagram -of-Shors -algorithm -Upper -register –
consists -of-2n-qubits -and-holds_fig1_228102587
Pasul al treilea implică verificarea parităț ii perioadei ob ținute.
Probabilitatea ca perioada cau tată sa fie impară este de (1
2)𝑘
, unde k este numă rul de
factori diferi ți ai lui N. Prin urmare, am avut 1−1
4=3
4 sanse ca perioada să fie un numar par.
Deoarece am avut norocul ca perio ada 𝑝=20 sa fie un număr par, putem trece la pasul
urmă tor din algoritm. În caz ca perioada nu era un numă r par, algoritmul trebuia reluat de la pasul
intai.
Pasul al patrulea ne pune in situaț ia de a calcula 𝑚𝑝
2−1 𝑚𝑜𝑑𝑢𝑙𝑜 143. Dacă rezultatul
este 0 atunci tr ecem la pasul 1, altfel continuă m algoritmul.
Deoarece 𝑚𝑝
2+1=510+1=13≠0 𝑚𝑜𝑑𝑢𝑙𝑜 143, putem trece la pasul urmă tor.
Pasul final al algoritmului lui Shor debutează cu determinarea 𝑡=gcd (𝑚𝑝
2−1,143 ) .
În urma calculelor obț inem 𝑡=gcd(11,143 )=11.
Deoarece 𝑚𝑝−1=0 mod 143 (deoarece 𝑝=20 este ordinul lui 𝑚=5 modulo 143),
avem 𝑚𝑝−1=(𝑚𝑝
2−1)(𝑚𝑝
2+1)=0 mod 143.

44
Deoarece 𝑚𝑝
2+1≠0, avem ca 𝑡 este un factor netrivial din descompunerea lui 143.
În concluzie, 11|143 și se obtine 143=11∙13.

Luna iunie, 2018, cel mai mare număr prim descoperit : 277232917−1.

45
Bibliografie

[1] BARNES, Connely, “Integer Factorization Algorithms”, Departament of Physics,
Oregon State University (2004)
[2] BAUMER, Elisa, SOBEZ, Jan -Grimo and TESSARINI, Stefan, “Shor’s
Algorithm” , (May 2015)
[3] CRILLY, Tony, “How Big is Infinity?”, Quercus Mathematics,UK, 2011
[4] GHISE, Lucica, “Elemente de teoria numerelor” , editura Rovimed (2017)
[5] LOMONACO, Samu el J.JR, “A lecture on Shor’s quantum factoring algorithm
version 1.1”, 2000 Mathematics Subject Classification (2000)
[6] RYAN, O’Donnel, “ Lecture 9: Shor’s Algorithm”, CMU 18 -859BB (2015)
[7] SHOR, Peter W., “Polynomial -Time Algorithms for Prime Fact orization and
Discrete Logarithms on a Quantum Computer” (1996)
[8] SIMION, Emil, NACCACHE, David, OPRINA, Andrei, “Criptografie si
securitatea informatiilor -Aplicatii”, editura Matrixrom (2011)
[9] STANCESCU, Stefan (Prof), MIHAI, Atena (Stud.), “Securi tatea pe internet.
Criptarea cuantica” , ETTI, UPB (2011)
[10] de WOLF, Ronald, “Quantum Computing” Lecture Notes

Referințe online :
[1] http://www.chalcedon.demon.co.uk/rgep/cartable.html

[2] http://www.maths.lancs.ac.uk/~jameson/carpsp.pdf

[3] Kiran Kedlaya, Is this number prime?, Berkeley Math Circle 2002 -2003

[4] http://www.cut -the-knot.org/blue/Euler.shtml

46