Teorema chineza a resturilor - generalizari si aplicatii

Scurta istorie

Se considera un numar de obiecte. Impartindu-le in grupuri de cate trei, raman doua negrupate. Impartindu-le in grupuri de cate cinci, raman trei. Impartindu-le in grupuri de cate sapte, raman doua. Cate obiecte sunt? Aceasta este problema enuntata de matematicianul chinez Sun-Tsu in secolul al IV-lea al erei noastre. El a demonstrat ca toate numerele naturale de forma 23 + 105 • k reprezinta solutiile acestei probleme. Din pacate nu putem sti daca a dezvoltat o metoda generala pentru a rezolva astfel de sisteme de ecuatii modulare. Aceasta este tema tratata in articolul care urmeaza.

Definitie

Pentru inceput, sa consideram sirul n = n ₁ , n ₂ , ..., n _k , ale carui elemente sunt, luate doua cate doua, prime intre ele.
*Teorema chineza a restului* (t.c.r.) afirma ca exista o corespondenta biunivoca intre orice numar a $\in$ Z _n si multimea ordonata de resturi ale lui a modulo n _i , i $\in$ {1, 2, ..., k}. Cu alte cuvinte, operatiile in Z _n pot fi aplicate echivalent atat pe numere cat si pe multimile ordonate corespunzatoare resturilor modulo n _i .
Pentru orice a, b $\in$ Z _n, notam a _i = a mod n, respectiv b _i = b mod n, generand corespondentele a $\leftrightarrow$ {a ₁ , a ₂ , ..., a _k } respectiv b $\leftrightarrow$ {b ₁ , b ₂ , ..., b _k }. Conform teoremei chineze a restului, pentru orice operator $\circ$ $\in$ {+, -, * }, a $\circ$ b $\leftrightarrow$ {(a ₁ $\circ$ b ₁) mod n ₁ , (a ₂ $\circ$ b ₂ )mod n ₂ , ..., (a _k $\circ$ b _k ) mod n _k } ramane o corespondenta valida.
Problema care se iveste imediat este conversia dintr-o forma in alta. Transformarea unui numar in multimea corespunzatoare este imediata. Partea mai dificila este operatia inversa, iar aceasta este problema care va fi tratata in continuare.
Pentru determinarea numarului x $\in$ Z _n , corespunzator multimii {a ₁ , a ₂ , ..., a _k }, este suficienta rezolvarea sistemului de ecuatii modulare:

 x $\equiv$ a ₁ (mod n ₁ )

x $\equiv$ a ₂ (mod n ₂ )

...

x $\equiv$ a _k (mod n _k )

Deoarece avem de a face cu o corespondenta biunivoca, conform teoremei, exista un singur x $\in$ Z _n care satisface sistemul de mai sus. Procedeul prin care se determina aceasta valoare nu este deosebit de complicat:

se noteaza n = n ₁ • n ₂ • ... • n _k si M _i = n / n _i (deoarece oricare doua valori n _i si n _j sunt prime intre ele, avem intotdeauna cmmdc(M _i, n _i ) = 1);
se calculeaza x _i , i $\in$ {1, 2, ..., k} cu proprietatea M _i • x _i $\equiv$ 1 (mod n _i ); cu alte cuvinte, avem x _i = M _i -1 mod n _i ;
se determina x = (a ₁ • M ₁ • x ₁ + a ₂ • M ₂ • x ₂ + ... + a _k • M _k • x _k) mod n.

Sa demonstram mai intai ca acesta valoare x satisface sistemul. Este necesar ca pentru orice i $\in$ {1, 2, ..., k}, x $\equiv$ a _i (mod n _i ).

Mai exact, trebuie sa fie satisfacuta egalitatea ((a ₁ • M ₁ • x ₁ + a ₂ • M ₂ • x ₂ + ... + a _k • M _k • x _k ) mod n) mod n _i = a _i , $\forall$ i $\in$ {1, 2, ..., k}.

Datorita faptului ca n _i | n, avem (a ₁ • M ₁ • x ₁ + a ₂ • M ₂ • x ₂ + ... + a _k • M _k • x _k ) mod n _i = a _i . Stim ca M _i = n / n _i, $\forall$ j $\neq$ i, M _j mod n _i = 0, deci $\forall$ j $\neq$ i, (a _j • M _j • x _j) mod n _i = 0. Este suficient sa demonstram ca (a _i • M _i • x _i ) mod n _i = a _i $\Leftrightarrow$ (a _i • (M _i • x _i ) mod n _i ) mod n _i = a _i . Folosind M _i • x _i $\equiv$ 1 (mod n _i) ajungem la egalitatea evidenta
a _i = a _i (q.e.d.)

Mai ramane de verificat daca valoarea x este unica. Fie x ^' o alta solutie; avem x < n si x ^' < n. Daca x $\equiv$ a _i (mod n _i ) si x ^' $\equiv$ a _i (mod n _i ), $\forall$ i $\in$ {1, 2, ..., k}, presupunand ca x ^' < x, avem x ^' - x $\equiv$ 0 (mod n _i ), $\forall$ i $\in$ {1, 2, ... k}.

Datorita faptului ca numerele n _i sunt relativ prime, rezulta ca x ^' - x = k • n, k $\in$ Z ^* , deci x ^' - x $\geq$ n, ceea ce contrazice ipoteza initiala. Asadar, solutia este unica, asa cum poate fi dedus si din t.c.r.

Mai mult, verificand daca se pastreaza corespondenta in cazul aplicarii operatorilor, demonstrarea t.c.r. poate fi usor incheiata.

Pentru calcularea inversului modular al unui numar din Z _n , de obicei se foloseste algoritmul

extins al lui Euclid . Evident, pentru ca acest invers sa existe, trebuie sa avem cmmdc(a, n) = 1. Aplicam algoritmul extins al lui Euclid si determinam x si y astfel incat a • x + n • y = 1 si obtinem a ^-1 = x mod n; pentru a verifica observam ca egalitatea a ^-1 = x mod n este echivalenta
cu a • (x mod n) $\equiv$ 1 (mod n) care, la rÃƒÂ¢ndul sau, este echivalenta cu a • x $\equiv$ 1 (mod n). Aceasta ultima afirmatie este evident adevarata deoarece avem a • x + n • y = 1.
Pentru valori mici ale lui n, este recomandata preprocesarea "bruta" a inverselor tuturor
numerelor a din Z _n prime cu n, folosind doua structuri repetitive imbricate.

acest articol trebuie imbunatatit

infoarena informatica de performanta

Teorema chineza a resturilor - generalizari si aplicatii

Scurta istorie

Definitie