Teorema chinezească a resturilor

De la Wikipedia, enciclopedia liberă

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.

Cuprins 1 Enunţ 1.1 Formulare alternativă şi generalizare 2 Note 3 Bibliografie

[modifică] Enunţ

Dacă n₁, n₂, …, n_k sunt întregi primi între ei doi câte doi, atunci, oricare ar fi întregii daţi a₁,a₂, …, a_k, 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 = n₁n₂…n_k.

[modifică] Formulare alternativă şi generalizare

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

Uneori, sistemul de congruenţe poate fi rezolvat chiar dacă numerele n_i' 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 n_i.

[modifică] Note

[modifică] Bibliografie

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