“Matematica este regina stiintelor si Teoria Numerelor este regina matematicii.”
Gauss

“Dumnezeu a inventat numerele intregi; restul este munca omului.”
Kronecker

Criptografia este un subiect interdisciplinar, intinzandu-se pe cateva domenii. Inaintea calculatoarelor, criptografia era strans legata de lingvistica. In prezent, criptografia foloseste drept suport domenii ale matematicii, in special unele dintre domeniile matematicii discrete. Aceasta include subiecte de teoria numerelor, teoria informatiei, statistica, combinatorica si altele.
Numerele prime si proprietatiile acestora au fost studiate intens de matematicienii din Grecia antica. Matematicienii scolii pitagoreice erau fascinati de studiul numerelor datorita proprietatilor mistice ale acestora. Ei au inteles inca de pe atunci ideea de primalitate si erau interesati in studiul numerelor perfecte si al numerelor prietene. In vremea aceea „Elementele” lui Euclid aparuta in jur de 300 i.Ch demonstra cateva rezultate importante despre numerele prime. Euclid a demonstrat ca exista o infinitate de numere prime. Aceasta este una dintre primele demonstratii cunoscute care foloseste metoda contradictiei ca sa stabileasca un rezultat.
La prima vedere, numerele prime par sa fie distribuite printre numerele intregi intr-un mod intamplator. De exemplu din 100 de numere luate din fata lui 10 000 000 sunt 9 numere prime, in timp ce tot in 100 de numere, dar dupa 10 000 000 sunt doar 2 prime.
In jur de 200 i.Ch matematicianul grec Eratostene a propus un algoritm pentru calculul numerelor prime numit Ciurul lui Eratostene.
Urmatorul pas important a fost facut de Fermat la inceputul secolului al 17-lea. Pana atunci Teoria Numerelelor a suferit perioade destul de nefaste. Fermat a demonstrat speculatiile lui Albert Girard ca fiecare numar prim de forma 4n+1 poate fi scris in mod unic ca suma de 2 patrate perfecte si a fost capabil sa demonstreze cum orice numar poate fi scris ca suma de patru patrate perfecte.
Fermat a propus o metoda de factorizare a numerelor mari pe care a demonstrat-o factorizand numarul 2027651281 = 44021*46061.El a demonstrat ceea ce avea sa devina cunoscuta sub denumirea de Mica teorema a lui Fermat.
Aceasta afirma ca daca p este un numar prim atunci pentru orice numar intreg a avem:
ap = a modulo p.
Aceasta formula a demonstrat jumatate din ceea ce a fost denumita „ipoteza chinezeasca”, veche de peste 2000 de ani, conform careia un numar intreg n este prim daca si numai daca numarul 2n – 2 este divizibil la n. Cealalta jumatate a acestei afirmatii este falsa, contradictia constinduiind-o faptul ca, de exemplu, 2341 - 2 este divizibil la 341, chiar daca numarul 341=31*11 este un numar compus. Mica teorema a lui Fermat constituie fundamentul pentru multe alte rezultate din Teoria Numerelor si reprezinta baza metodelor de verificare a primalitatii unui numar, metode folosite pe scara larga in domeniul calculatoarelor.
Fermat a corespondat cu alti matematicieni ai vremurilor lui si in particular cu calugarul Marin Merssene. Intr-una din scrisorile sale catre Mersenne, Fermat a lansat ipoteza ca numerele 2n + 1 ar fi intotdeauna prime daca n este o putere a lui 2. El a verificat aceasta pentru n = 1, 2, 4, 8 si 16 si stia ca daca n nu era o putere a lui 2, rezultatul esua. Numerele de aceasta forma sunt numite Numere Fermat si nu au trecut mai mult de 100 de ani pana cand Euler a aratat ca in urmatorul caz 232 + 1 = 4294967297 este divizibil la 641, deci nu este prim.
Descoperirile lui Euler au avut un impact deosebit asupra Teoriei Numerelor in general si asupra numerelor prime in particular. El a extins Mica Teorema a lui Fermat si a introdus functia a lui Euler. Cum am mentionat anterior el a factorizat al 5-lea numar Fermat 232 + 1, a gasit 60 de perechi de numere prietene si a stabilit (dar a fost neputincios sa demonstreze ) ceea ce a devenit cunoscuta drept Legea Reciprocitatii Patratice.
Euler a fost primul care a realizat ca teoria numerelor poate fi studiata folosind unelte ale analizei matematice. El a aratat ca nu numai asa-numita serie armonica (1/n) este divergenta, dar si seria
1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... formata prin insumarea inverselor numerelor prime este tot divergenta.
S-ar putea pretinde ca analiza matematica a început cu Euler.
Euler a contribuit la cunoasterea a multor alte domenii, si în toate a implicat cunostintele sale de matematica si aptitudinile sale.

Contributia lui Euler la dezvoltarea matematicii

Cel mai reprezentativ matematician al sec.XVIII este Leonhard Euler (15 aprilie 1707 – 18 septembrie 1783), supranumit „Analiza incarnata”. Fiu de pastor, nascut la Basel, studiaza teologia, urmand sa succeada tatalui sau, Paul, dar –din fericire pentru matematica- Jacques Bernoulli (ca profesor), precum si Daniel si Nicolas III (ca prieteni si colegi) il atrag spre matematici. Cand in 1725 acestia doi pleaca la Petersburg, tanarul Euler ii urmeaza. Astfel ca, pana in 1741, Euler lucreaza la Academia din Petersburg. Aici Euler se cunoaste cu Christian Goldbach, care in 1742 emite ipoteza conform careia orice numar par mai mare ca 2 se poate descompune in suma a doua numere prime (ramasa pana azi „ipoteza lui Goldbach”).
Intre anii 1741-1766 (pe timpul lui Frederic cel Mare) Euler lucreaza la Berlin. In 1766 cand Euler era aproape orb, Ecaterina a II-a il recheama la Petersburg, unde ramane pana la moarte.
Desi la 28 de ani isi pierde un ochi (din cauza oftalmiei), iar la 59 de ani orbeste complet, Euler isi continua munca. In aceasta perioada el este ajutat de catre un ginere si de fiul sau mai mare, Johann Albrecht.
Problema de astronomie propusa de academia din Paris pentru rezolvare in termen de 3 luni, Euler o rezolva in 3 zile! Efortul extraordinar l-a costat ochiul drept. Reintors de la Berlin, cataracta ii ataca si ochiul stang. Desi operatia reuseste, in urma unei infectii orbeste complet. Dar memoria sa deosebita il ajuta sa munceasca in continuare.Astfel, doi studenti calculand suma unei serii, obtin la a 15-a zecimala diferenta de o unitate. Refacand mintal calculele, Euler gaseste greseala!
A scris un numar mare de lucrari, in toate domeniile matematice.

Numere Euler Pseudoprime

Un numar intreg impar compus n este numit numar Euler pseudoprim relativ la baza a daca a si n sunt prime intre ele si:

Primele cateva numere Euler pseudoprime cu baza 2 sunt 341, 561, 1105, 1729, 1905, 2047, ... .
Motivul pentru aceasta definitie il constitue faptul ca toate numerele prime p satisfac aceasta ecuatie care poate fi dedusa din Mica Teorema a lui Fermat. Mica Teorema a lui Fermat afirma ca daca p este prim si (a,p)=1 atunci ap-1 = 1 (mod p).
Presupunand ca p>2 este prim atunci p poate fi exprimat ca si p=2q+1, unde q este un numar intreg. Astfel: a(2q+1)-1 = 1 (mod p) care inseamna ca a2q - 1 = 0 (mod p).
Aceasta poate fi factorizat ca si (aq - 1)(aq + 1) = 0 (mod p) care este echivalent cu
a(p-1)/2 = ±1 (mod p).
Aceasta ecuatie poate fi folosita mai corect si mai rapid si poate fi utilizata pentru testarea probabilistica a primalitatii. Aceste teste sunt de doua ori mai puternice decat testele bazate pe Mica Teorema a lui Fermat.
Orice numar Euler pseudoprim este si Fermat pseudoprim. Nu este posibila producerea unui anumit test de primalitate bazat pe stabilirea faptului daca un numar este Euler pseudoprim sau nu deoarece exista numere Euler tare pseudoprime, numere care sunt numere Euler pseudoprime relativ la orice baza de la orice baza relativ prima pana la ele insele.
Numerele Euler tare pseudoprime sunt o submultime a numerelor Fermat absolut prime, sau a numerelor Carmichael, iar cel mai mic numar Euler tare pseudoprim este 1729 = 7·13·19.
Trebuie mentionat faptul ca acea conditie de numere Euler tare pseudoprime adica conditia ca a(n-1)/2 = (a/n) (mod n), unde (a,n)=1 si (a/n) este simbolul lui Jacobi,
este uneori folosita pentru definitia unui numar Euler pseudoprim.
Numere Euler-Jacobi pseudoprime
In teoria numerelor, un numar intreg n impar, compus se numeste Euler-Jacobi pseudoprim relativ la baza a daca (a,n)=1 si
a(n - 1)/2 = (a/n) (mod n),
unde (a/n) este simbolul lui Jacobi .
Motivul acestei definitii este faptul ca toate numerele prime n care satisfac ecuatia de mai sus sunt folosite si in descrierea simbolului lui Legendre. Ecuatia poate fi folosita cu o rapiditate mai mare decat formulele folosite in testarea probabilistica a probabilitatii. Aceste teste sunt de doua ori mai puternice decat testele bazate pe Mica Teorema a lui Fermat.
Orice numar Euler-Jacobi pseudoprim este si Fermat pseudoprim si Euler pseudoprim. Nu exista numere care sunt Euler-Jacobi pseudoprime relativ la toate bazele asa cum sunt numerele Carmichel. Solovay si Strassen au aratat ca pentru orice numar compus n, pentru cel putin n/2 baze mai mici decat n, n nu este un numar Euler-Jacobi pseudoprim.
Trebuie mentionat, din nou ca aceste numere sunt numite in unele articole numere Euler pseudoprime.
Simbolul lui Jacobi

Simbolul lui Jacobi, notat (a/n) este o functie care este definita in termenii simbolului lui Jacobi. Daca descompunerea in factori primi a lui n este n=p1e1 *...*pkek atunci simbolul lui Jacobi este definit ca si (a/n) =(a/p1)e1 *...*(a/pk)ek.
De mentionat ca (a|1) = 1 pentru toate numerele intregi a.
Jacobi a generalizat simbolul lui Legendre pentru a permite si utilizarea unor numere care sunt impare, dar nu neaparat prime.

Simbolul lui Legendre

Presupunem ca p este un numar impar prim si a este un numar intreg oarecare. Simbolul lui Legendre (a|p) se defineste ca fiind:

+1 daca a este un rest patratic (mod p),
-1 daca a este un non-rest patratic (mod p) si
0 daca p divide a
Nota: simbolul lui Legendre este mai bine scris pe verticala: , dar este dificil de scris pe paginile de internet.
In studiul ecuatiilor diofantiene (si surprinzator adesea in studiul numerelor prime ) este important de stiut daca numarul intreg a este patratul unui intreg modulo p. Daca este, spunem ca a este un rest patratic modulo p, altfel a este un non-rest patratic modulo p.
De exemplu :
42=7 (mod 9) astfel 7 este un rest patratic modulo 9.
Alte exemple:
modulo Rest patratic Rest
non-patratic
2 0,1 (none)
3 0,1 2
4 0,1 2,3
5 0,1,4 2,3
6 0,1,3,4 2,5
7 0,1,2,4 3,5,6
8 0,1,4 2,3,5,6,7
Pentru un numar impar p sunt (p+1)/2 resturi patratice (continand zero) si (p-1)/2 non-resturi. (Resturile provin de la numerele 02, 12, 22, ... , {(p-1)/2}2, acestea sunt toate diferite modulo p).
Cand baza este produsul unei puteri prime impare, si numerele din cerinta sunt prime intre ele cu baza, atunci:
• produsul a doua resturi sau doua non-resturi este un rest
• produsul dintre un rest care nu este zero-divizor si un non-rest este un non-rest.
Unul dintre cele mai importante rezultate ale resturilor patratice este exprimat in dificultatea demonstrarii teoremei de reciprocitate patratica.
Euler a aratat ca (a|p) = a (p-1)/2 (mod p). Folosind acest rezulta putem arata urmatoarele:
Fie p si q doua numere prime impare, atunci
(-1|p) = 1 daca p = 1 (mod 4), si (-1|p) = -1 daca p = 3 (mod 4);
(a|p) (b|p) = (ab|p);
Daca a = b (mod p), atunci (a|p) = (b|p);
(a2|p) = 1 in afara de faptul cand p divide a.
Pentru numarul prim 2 avem:
(2|p) = 1 daca p = 1 sau 7 (mod 8), si
(2|p) = -1 daca p = 3 sau 5 (mod 8).
Simbolul lui Legendre este adesea evaluat utilizand simbolul lui Jacobi.
Tinand cont ca al doilea termen din simbolul lui Legendre ,(a|p), denumit si , ar putea fi prim, Jacobi a generalizat simbolul lui Legendre pentru a permite intrari si pentru numerele impare (care nu sunt necesar prime) ca si urmatoarele:
Fie factorizarea lui n = . Atunci

Se observa ca (a|1) = 1 pentru toate numerele intregi a.
Acest simbol (ce arata la fel ca si simbolul lui Legendre) este simbolul lui Jacobi .
Pentru simbolul lui Jacobi , (a|n)=1 nu inseamna neaparat ca a este un rest patratic al lui n. De exemplu, (8|15) = 1, dar 8 nu este rest patratic al lui 15.
Simbolul lui Jacobi are multe proprietati care fac folosirea lui cel mai simplu mod de a evalua un simbol Legendre. Presupunand ca m si n sunt numere intregi impare si a si b sunt numere intregi aleatoare, simbolul lui Jacobi satisface urmatoarele:
• (a|n)=0 daca cmmdc(a,n) > 1.
• (-1|n) = 1 daca n = 1 (mod 4), si (-1|n) = -1 daca n = 3 (mod 4);
• (a|n) (b|n) = (ab|n);
• (a|m) (a|n) = (a|mn);
• daca a = b (mod n), atunci (a|n) = (b|n).
Pentru numarul prim 2 avem
• (2|n) = 1 daca n = 1 sau 7 (mod 8), si
• (2|n) = -1 daca n = 3 sau 5 (mod 8).
In sfarsit si probabil cea mai folositoare relatie, daca cmmdc(a,n) =1 si a este impar pozitiv
•

In tabelul de mai jos sunt date toate numerele Euler-Jacobi pseudoprime mai mici decat 10000 pentru cateva baze prime a. Acest tabel este totusi, in proces de a fi verificat si trebuie folosit cu precautie pana cand se va stii sigur daca numerele indicate sunt corecte.
a
2 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481
3 121, 1729, 2821, 7381, 8401
5 781, 1541, 1729, 5461, 5611, 6601, 7449
7 25, 703, 2101, 2353, 2465, 3277
11 133, 793, 2465, 4577, 4921, 5041, 5185
13 105, 1785, 5149, 7107, 8841, 9577, 9637
17 9, 145, 781, 1305, 2821, 4033, 5833, 6697
19 9, 45, 49, 169, 1849, 2353, 3201, 4033, 4681, 6541, 6697, 8281
23 169, 265, 553, 1729, 2465, 4033, 4681, 6533, 6541, 7189, 8321, 8911
29 91, 341, 469, 871, 2257, 5149, 5185, 6097, 8401, 8841
31 15, 49, 133, 481, 2465, 6241, 7449, 9131
37 9, 451, 469, 589, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271
41 21, 105, 841, 1065, 1281, 1417, 2465, 2701, 3829, 8321
43 21, 25, 33, 77, 105, 185, 385, 481, 561, 777, 825, 973, 1105, 1541, 1729, 1825, 2465, 2553, 2821, 2849, 3281, 3439, 3781, 4033, 4417, 6105, 6369, 6545, 6601, 6697, 7825
47 65, 69, 341, 345, 481, 561, 703, 721, 793, 897, 1105, 1649, 1729, 1891, 2257, 2465, 2737, 3145, 3201, 5185, 5461, 5865, 6305, 9361
53 9, 65, 91, 117, 561, 585, 1105, 1441, 1541, 1729, 2209, 2465, 2529, 2821, 2863, 3097, 3367, 3481, 3861, 5317, 5833, 6031, 6433, 9409
59 145, 451, 561, 645, 1105, 1141, 1247, 1541, 1661, 1729, 1991, 2413, 2465, 3097, 4681, 5611, 5729, 6191, 6533, 6601, 7421, 8149, 8321, 8705, 9637
61 15, 93, 217, 341, 465, 1261, 1441, 1729, 2465, 2821, 3565, 3661, 4061, 4577, 5461, 6541, 6601, 6697, 7613, 7905, 9305, 9937
67 33, 49, 217, 385, 561, 1105, 1309, 1519, 1705, 1729, 2209, 2465, 3201, 5797, 7633, 7701, 8029, 8321, 8371, 9073

In teoria numerelor un numar probabil prim (PRP) este un numar intreg ce satisface o conditie satisfacuta de toate numerele prime. Deoarece exista numere probabil prime care sunt numere compuse (numite pseudoprime) acestea sunt rare si depind de testul utilizat.
Testele Fermat pentru numere compuse, care folosesc Mica Teorema a lui Fermat se bazeaza pe urmatoarele argumente: fiind dat un numar intreg n, se aleg cateva numere intregi a prime cu n si se calculeaza an - 1 mod n. Daca rezultatul este diferit de 1, n este numar compus. Daca rezultatul este 1 numarul ar putea fi sau ar putea sa nu fie prim; atunci n este numit un numar slab probabil prim relativ la baza a.
Testele Fermat pot fi imbunatatite utilizand faptul ca singurele radacini patratice ale lui 1 modulo a sunt 1 si -1. Numerele care par a fi prime dupa acest test mai puternic sunt cunoscute ca numere tare probabil prime relativ la baza a.
Un numar Euler probabil prim este un numar intreg ce pare a fi prim printr-o teorema mult mai puternica ce spune ca pentru orice numar prim p si pentru orice a, a(p - 1)/2 = (a/p) modulo p, unde (a/p) este simbolul lui Legendre. Acest test este la fel de eficient dar este de 2 ori mai puternic decat testul Fermat. Un numar Euler probabil prim care este numar compus, este numit numar Euler-Jacobi pseudoprim.
Primalitatea probabila este o baza pentru algoritmi eficienti de testare a primalitatii. Acesti algoritmi au largi intrebuintari in criptografie. Se poate spune despre acestia ca sunt de obicei probabilistici prin natura lor. Ideea este ca in timp ce exista numere compuse relativ la baza a, probabil prime pentru orice a fixat, putem inversa rolurile: pentru orice n compus,fixat si un a ales la intamplare, putem spera ca n nu este un numar probabil prim relativ la baza a, cu probabilitate destul de ridicata.
Aceasta afirmatie este din nefericire falsa pentru numerele slab probabil prime, deoarece in aceasta categorie de numere exista numerele Carmichael; dar este adevarata pentru multe notiuni rafinate ale probabil primalitatii, ca si numere tari probabil prime( algoritmul Miller-Rabin) sau Euler probabil prime(algoritmul Solovay-Strassen).
Chiar si atunci cand este necesara o demonstratie pentru determinarea primalitatii, un prim pas necesar este testarea probabil primalitatii.
Un PRP test este cateodata combinat cu un tabel al numerelor mici pseudoprime pentru o stabilire mai rapida a primalitatii unui numar dat mai mic decat numarul de plecare.

Numere tari Pseudoprime

Un numar tare pseudoprim relativ la baza a este un numar impar compus n cu

Un numar tare pseudoprim relativ la baza a este un numar impar compus n (cu d impar)
pentru care avem:

(1)

sau

(2)

pentru orice r = 0, 1, ..., s-1(Riesel 1994, p. 91).
Definitia este motivata de faptul ca un numar Fermat pseudoprim n relativ la baza b satisface:

(3)

Dar deoarece n este impar, el poate fi scris ca: n=2m+1, si:

(4)

Daca n este prim, el trebuie sa divida cel putin unul dintre factori, dar nu-i poate divide pe amandoi deoarece atunci ar divide diferenta lor

(5)

de aceea,

(6)

asa scriind

se obtine :

(7)