Teorema chinezească a resturilor

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Teorema chinezească a resturilor este un rezultat din teoria numerelor, cu aplicații în criptografie. Teorema a fost cunoscută de matematicienii chinezi din secolul al III-lea, apărând într-o carte a matematicianului Sun Tzu, și apoi, în 1247, într-o altă carte a lui Qin Jiushao.

Enunț[modificare | modificare sursă]

Dacă n1, n2, …, nk sunt întregi primi între ei doi câte doi, atunci, oricare ar fi întregii dați a1,a2, …, ak, există un întreg x care este soluție a următorului sistem de congruențe[1]:

\begin{align}
 x &\equiv a_1 \pmod{n_1} \\
 x &\equiv a_2 \pmod{n_2} \\
   &\vdots \\
 x &\equiv a_k \pmod{n_k}
\end{align}

Mai mult, toate soluțiile x ale acestui sistem sunt congruente modulo produsul N = n1n2nk.

Formulare alternativă și generalizare[modificare | modificare sursă]

Deci  x\equiv y \pmod{n_i} pentru orice 1\leq i \leq k, dacă și numai dacă x \equiv y \pmod{N}.

Uneori, sistemul de congruențe poate fi rezolvat chiar dacă numerele ni' nu sunt prime între ele două câte două. O soluție x există dacă și numai dacă:

a_i \equiv a_j \pmod{cmmdc(n_i,n_j)} \qquad \forall i, j. \,\!

Toate soluțiile x sunt, atunci, congruente modulo cel mai mic multiplu comun al numerelor ni.

Note[modificare | modificare sursă]

  1. ^ Menezes, p. 68

Bibliografie[modificare | modificare sursă]

  • Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott. Handbook of Applied Cryptography