== include(page="template/implica-te/scrie-articole" user_id="MciprianM") ==

(Categoria _Matematica_, Autor _Adrian Vladu_)
 

h2. 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 <tex>23 + 105 * k</tex> 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.

<tex>x \equiv a_2 (mod\ n_2)</tex>.
Cu alte cuvinte, sistemul si noua ecuatie sunt echivalente.

Daca deteriminam valoarea <tex>x</tex> minima care satisface sistemul de ecuatii modulare, toate celelalte solutii vor fi obtinute adunand la acesta un multiplu al celui mai mic multiplu comun al numerelor <tex>n_1, n_2, ..., n_k</tex>. Din <tex>n_1 * b_1 + a_1 = n_2 * b_2 + a_2</tex> se obtine <tex>n_1 * b_1 - n_2 * b_2 = a_2 - a_1</tex>. Fie <tex>d = cmmdc(n_1, n_2)</tex>. Aplicand "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid se determina valorile <tex>c_1</tex> si <tex>c_2</tex> astfel incat <tex>n_1 * c_1 + n_2 * c_2 = d</tex>. Amplificand cu <tex>(a_2 - a_1) / d</tex> se obtine: <tex>n_1 * c_1 * (a_2 - a_1) / d + n_2 * c_2 * (a_2 - a_1) / d = a_2 - a_1</tex>. Am putea fi tentati sa credem ca <tex>b_1 = c_1 * (a_2 - a_1) / d</tex> si <tex>b_2 = c_2 * (a_2 - a_1)</tex>, dar aceasta nu este intotdeauna cea mai buna solutie. Fie <tex>h = cmmmc(n_1, n_2)</tex>, valoarea minima pentru care, daca <tex>x</tex> este solutie, atunci si <tex>x + h</tex> este solutie (cu alte cuvinte, <tex>h</tex> este perioada). Notand <tex>l = (a_2 - a_1) / d</tex>, observam ca <tex>n_1 * c_1 * l - n_2 * c_2 * l + k * h - k * h = n_1 * (c_1 * l + k * h / n_1) - n_2 * (c_2 * l + k * h/ n_2)</tex> satisface sistemul. Dorim sa gasim cea mai mica solutie, deci valoarea <tex>c_1 * l + k * h / n_1</tex> trebuie sa fie cat mai mica posibil. Fie <tex>m_1 = c_1 * l + k * h / n_1</tex>, iar <tex>n_1 * m_1 + b_1</tex> cea mai mica valoare care satisface sistemul. Stim ca <tex>n_1 * m_1 + b_1 < h</tex> si exista o singura solutie mai mica decat <tex>h</tex>. Avem <tex>h / n_1 > m_1 \geq 0</tex>, deci <tex>m_1 = (c_1 * l)\ mod\ (h / n_1)</tex>. Sistemul format din cele doua ecuatii este satisfacut pentru valorile <tex>x = cmmmc(n_1, n_2) * i + n_1 * m_1 + b_1</tex>, pentru <tex>i \geq 0</tex>. Sistemul este astfel echivalent cu <tex>x \equiv n_1 * m_1 + b_1 (mod\ cmmmc(n_1, n_2))</tex>.

Daca deteriminam valoarea <tex>x</tex> minima care satisface sistemul de ecuatii modulare, toate celelalte solutii vor fi obtinute adunand la acesta un multiplu al celui mai mic multiplu comun al numerelor <tex>n_1, n_2, ..., n_k</tex>. Din <tex>n_1 * b_1 + a_1 = n_2 * b_2 + a_2</tex> se obtine <tex>n_1 * b_1 - n_2 * b_2 = a_2 - a_1</tex>. Fie <tex>d = cmmdc(n_1, n_2)</tex>. Aplicand "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid se determina valorile <tex>c_1</tex> si <tex>c_2</tex> astfel incat <tex>n_1 * c_1 + n_2 * c_2 = d</tex>. Amplificand cu <tex>(a_2 - a_1) / d</tex> se obtine: <tex>n_1 * c_1 * (a_2 - a_1) / d + n_2 * c_2 * (a_2 - a_1) / d = a_2 - a_1</tex>. Am putea fi tentati sa credem ca <tex>b_1 = c_1 * (a_2 - a_1) / d</tex> si <tex>b_2 = c_2 * (a_2 - a_1)</tex>, dar aceasta nu este intotdeauna cea mai buna solutie.
 
Fie <tex>h = cmmmc(n_1, n_2)</tex>, valoarea minima pentru care, daca <tex>x</tex> este solutie, atunci si <tex>x + h</tex> este solutie (cu alte cuvinte, <tex>h</tex> este perioada). Notand <tex>l = (a_2 - a_1) / d</tex>, observam ca <tex>n_1 * c_1 * l - n_2 * c_2 * l + k * h - k * h = n_1 * (c_1 * l + k * h / n_1) - n_2 * (c_2 * l + k * h/ n_2)</tex> satisface sistemul. Dorim sa gasim cea mai mica solutie, deci valoarea <tex>c_1 * l + k * h / n_1</tex> trebuie sa fie cat mai mica posibil. Fie <tex>m_1 = c_1 * l + k * h / n_1</tex>, iar <tex>n_1 * m_1 + b_1</tex> cea mai mica valoare care satisface sistemul. Stim ca <tex>n_1 * m_1 + b_1 < h</tex> si exista o singura solutie mai mica decat <tex>h</tex>. Avem <tex>h / n_1 > m_1 \geq 0</tex>, deci <tex>m_1 = (c_1 * l)\ mod\ (h / n_1)</tex>. Sistemul format din cele doua ecuatii este satisfacut pentru valorile <tex>x = cmmmc(n_1, n_2) * i + n_1 * m_1 + b_1</tex>, pentru <tex>i \geq 0</tex>. Sistemul este astfel echivalent cu <tex>x \equiv n_1 * m_1 + b_1 (mod\ cmmmc(n_1, n_2))</tex>.

Pentru a rezolva un sistem de ecuatii cu mai mult de doua necunoscute este suficient sa aplicam succesiv operatiile descrise mai sus, reducand perechile de ecuatii la una singura echivalenta, pana cand ramane o singura ecuatie modulara.
Limbajele de programare evalueaza gresit operatiile de forma $*a mod n*$ , atunci cand $a$ este un numar intreg negativ. Pentru a evita neplacerile ar trebui implementata o functie proprie pentru operatia modulo. Un exemplu este prezentat in continuare:
==code(c) |
int mod(int a, int n) {

    return a >= 0 ?
        a % n :
        n - ((-a) % n);

    a %= n;
    if (a < 0) a += n;
    return a;

}
==

Se considera o informatie secreta codificata intr-un numar foarte mare <tex>N</tex>. Pentru a-l pastra in siguranta, acesta este impartit la <tex>n</tex> servere din tara. Daca <tex>p</tex> servere nu functioneaza, din diverse motive, <tex>N</tex> poate fi recuperat folosind <tex>n-p</tex> servere ramase, atata timp cat <tex>n-p \geq k</tex>, valoarea threshold.

Alegand <tex>n</tex> numere prime <tex>p_1, p_2, ..., p_n</tex>, cuprinse intre <tex>N^{1/k}</tex> si <tex>N^{1/(k-1)}</tex>, <tex>N</tex> poate fi determinat folosind exact <tex>k</tex> servere, dar niciodata mai putine. Fiecare server <tex>i</tex> primeste catul si restul impartirii lui <tex>N</tex> la <tex>p_i</tex>. Pentru reconstituire se foloseste _t.c.r_, obtinandu-se astfel valoarea <tex>N</tex> cautata. Acest lucru este posibil deoarece alegand, fara a restrange generalitatea, primele <tex>k</tex> servere, se obtine o solutie modulo <tex>p_1 * p_2 * ... * p_k</tex>.
Vom avea intotdeauna <tex>p_i > N^{1/k} * p_1 * p_2 * ... * p_n > N</tex>.
Toate solutiile vor fi de forma $x = (p{~1~} * p{~2~} * ...  * p{~n~}) * i + x{~0~}$;
dat fiind faptul prezentat anterior, ne intereseaza doar solutia cu $i = 0$.
Presupunand ca se iau in considerare $r < k$ servere, se obtin (din nou fara a restrange generalitatea) solutii de forma $x = (p{~1~} * p{~2~} * ...  * p{~r~})  * i + x{~0~}$.
Un adversar care cunoaste $r$ secrete poate itera dupa $i$, incercand toate valorile posibile ale lui $x$.
Desi initial am putea crede ca solutia va fi gasita usor, alegand o valoare $p{~i~}$ mult mai mica decat $N^1/(k-1)^$, solutia generala va fi de forma $x = M * i + x{~0~}$, unde $M$ este mult mai mic decat $N$, aceasta lasand intrusului un numar imens de incercari, iar ghicirea valorii corecte devine practic imposibila.

Alegand <tex>n</tex> numere prime <tex>p_1, p_2, ..., p_n</tex>, cuprinse intre <tex>N^{1/k}</tex> si <tex>N^{1/(k-1)}</tex>, <tex>N</tex> poate fi determinat folosind exact <tex>k</tex> servere, dar niciodata mai putine. Fiecare server <tex>i</tex> primeste catul si restul impartirii lui <tex>N</tex> la <tex>p_i</tex>. Pentru reconstituire se foloseste _t.c.r_, obtinandu-se astfel valoarea <tex>N</tex> cautata. Acest lucru este posibil deoarece alegand, fara a restrange generalitatea, primele <tex>k</tex> servere, se obtine o solutie modulo <tex>p_1 * p_2 * ... * p_k</tex>. Vom avea intotdeauna <tex>p_i > N^{1/k} * p_1 * p_2 * ... * p_n > N</tex>. Toate solutiile vor fi de forma <tex>x = (p_1 * p_2 * ...  * p_n) * i + x_0</tex>; dat fiind faptul prezentat anterior, ne intereseaza doar solutia cu <tex>i = 0</tex>. Presupunand ca se iau in considerare <tex>r < k</tex> servere, se obtin (din nou fara a restrange generalitatea) solutii de forma <tex>x = (p_1 * p_2 * ...  * p_r)  * i + x_0</tex>. Un adversar care cunoaste <tex>r</tex> secrete poate itera dupa <tex>i</tex>, incercand toate valorile posibile ale lui <tex>x</tex>. Desi initial am putea crede ca solutia va fi gasita usor, alegand o valoare <tex>p_i</tex> mult mai mica decat <tex>N^{1/(k-1)}</tex>, solutia generala va fi de forma <tex>x = M * i + x_0</tex>, unde <tex>M</tex> este mult mai mic decat <tex>N</tex>, aceasta lasand intrusului un numar imens de incercari, iar ghicirea valorii corecte devine practic imposibila.

h2. Bibliografie

# Donald E. Knuth, The Art of Computer Programming vol. 2 - Seminumerical Algorithms
# Sarad A.V aka Data, Applications to Chinese Remainder Theorem
# @***@ "Internet Problem Solving Contest 2005, Problem G - Gears in Action":http://ipsc.ksp.sk/contests/ipsc2005/real/problems/g.php

 
*Articol scris de Adrian Vladu preluat din Ginfo nr.16/1 - ianuarie 2006*

3685