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]:

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

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

Deci pentru orice , dacă și numai dacă .

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ă:

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