Teorema chineza a resturilor

Cozianu Robert - Zoltan

Universitatea ”Petru Maior”, Târgu Mureș

1 iulie 2014

1

Cuprins1 Introducere-Functionare 3

2 Demonstratie 3

3 Exemplu 5

4 Utilizare 5

2

Rezumat

Aceasta teorema este utilizata in matematica pentru a afla un nu-mar cu ajutorul unor resturi obtinute din impartirea acestuia. Faptulca un numar poate fi aflat cu ajutorul altor numere mai mici, face caaceasta teorie sa fie utilizata des in criptografie.

1 Introducere-FunctionareTeorema chineza a resturilor (TCR) ajuta la aflarea unui numar intreg

daca sunt cunoscute resturile impartirii acestui numar la mai multe numereal caror cmmdc este 1. Aceasta problema a fost studiata temeinic de catrematematicienii chinezi ın urma cu mai bine de 2000 de ani. A fost publi-cata prima oara in secolele 3-4 de catre matematicianul Sun-Tzu. Cerintaproblemei a fost „Sa se gaseasca un numar care împarţit prin 3, 5, 7 sa dearesturile 2, 3, respectiv 4”. Putem crede ca aceasta teorema a fost des utili-zata in trecut pentru a calcula numarul soldatilor dintr-o armata. Acestorali s-a cerut sa se grupeze de mai multe ori in grupe egale (grupe care au fostrelativ prime intre ele), iar de fiecare data s-a notat numarul soldatilor careau ramas fara grupa. Exista mai multi algoritmi cu ajutorul careia se poatecalcula solutia, cea mai raspandita este algoritmul lui Euclid, prezentat maijos, dar mai exista algoritmul lui Gauss, algoritmul lui Garner si algoritmulART (Aryabhata Remainder Theorem). Pe langa acestea mai exista metodalui Lagrange¸ si metoda lui Newton.Rezolvarea acestei probleme este foarte utila pentru calculul factorizarilorcomplete ale polinoamelor cu coecienti ıntregi. Aceasta teorema este des uti-lizata in criptografie, deoarece ajuta la memorarea unor numere mari subforma a a doi vectori de numere considerabil mai mici.

2 DemonstratieCel mai raspandit algoritm pentru demonstrarea acestei teoreme este al-

goritmul lui Euclid.

Sa consideram șirul m1, m2, . . . , mr , unde mi ∈ N si ale carui elemente sunt,luate doua câte doua, prime între ele. Atunci, pentru orice numere întregia1, . . . , ak, exista un numar întreg x care satisface urmatorul sistem de ecuaţiimodulare:

3

x ≡ a1(mod m1)x ≡ a2(mod m2)

…x ≡ an(mod mn)

Pentru a gasi xn, trebuie sa calculam ecuatia

xn = (B1 ∗ z1 ∗m1) + (B2 ∗ z2 ∗m2) + . . . + (Bn ∗ zn ∗mn).

folosind

B = m1 ∗m2 ∗ . . . ∗mn

primim

Bi = Bmi

.

Pentru a calcula zi avem formula

Bi ∗ zi = 1 (mod mi)

Observam ca Bi trebuie inmultit cu un numar zi pentru ca rezultatul imparţitla mi sa dea rest 1.In caz ca este posibil, din Bi se scade cel mai mare multiplu al lui mi.

Pentru a obtine cel mai mic numar ce rezolva sistemul de mai sus, serezolva:

x1 = xn (mod B)

4

3 Exemplux ≡ 2(mod 3)x ≡ 3(mod 5)x ≡ 2(mod 7)

B = 3 ∗ 5 ∗ 7 = 105

B1 = 1053 = 35

B2 = 1055 = 21

B3 = 1057 = 15

z1 : 35 ∗ z1 ≡ 1 (mod 3)⇒ z1 = 2; (70÷3 = 23 rest 1)

z1 : 21 ∗ z2 ≡ 1 (mod 5)⇒ z2 = 1;

z1 : 15 ∗ z3 ≡ 1 (mod 7)⇒ z3 = 1;

x = (35 ∗ 2 ∗ 2) + (21 ∗ 1 ∗ 3) + (15 ∗ 1 ∗ 2)(mod105) = 233(mod105) = 23

23 este cea mai mica valoare care satisface sistemul.

Verificare:

23÷ 3 = 7 rest 223÷ 5 = 4 rest 323÷ 7 = 3 rest 2

4 UtilizareDupa cum se observa, cunoașterea unei rezolvari pentru acest tip de sistemajuta la memorarea unor numere mari sub forma a doi vectori de numereconsiderabil mai mici. Aceasta face ca teorema Chineza a resturlor sa aiba omare importanţa în domeniul criptografiei și a securitaţii informaţiei, acolounde ascunderea datelor este cruciala.

5

Bibliografie

http://www.infoarena.ro/teorema-chineza-a-resturilor

http://web.info.uvt.ro/ mmarin/lectures/CSI/CSI-10.pdf

http://en.wikipedia.org/wiki/ChineseremaindertheoremRSAAlgorithm

http://pages.pacificcoast.net/ cazelais/222/chineserem.pdf

6