Chińskie twierdzenie o resztach

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Chińskie twierdzenie o resztach mówi, że układ kongruencji:

...

(gdzie y1, y2, ..., yk są dowolnymi liczbami całkowitymi, a liczby n1, n2, ..., nk to liczby parami względnie pierwsze), spełnia dokładnie jedna liczba

'[1].

Jest to jedno z najważniejszych twierdzeń w teorii liczb i kryptografii.

Nazwa twierdzenia związana jest z chińskim matematykiem Sun Zi, który około roku 100 naszej ery rozwiązał problem znajdowania tych liczb całkowitych, które przy dzieleniu przez 3, 5 oraz 7 dają odpowiednio reszty 2, 3 i 2[1].

Algorytm rozwiązywania układu kongruencji[edytuj kod]

Istnieje algorytm wyliczania na podstawie takiego układu równań.

Mianowicie, niech

oraz Mi = M / ni (ik). Wówczas na podstawie założenia oraz są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie liczby całkowite fi, gi (ik), że

Niech ei = giMi (ik). Wówczas

oraz

gdy ji. Wtedy x zdefiniowany wzorem

spełnia powyższy układ kongruencji, jest to jedno z rozwiązań - pozostałe różnią się o wielokrotność M.

Przykład[edytuj kod]

Dany jest układ kongruencji:

,
,
.

Używając metody generowania kolejnych wielokrotności (która jest mało wydajnym algorytmem, aczkolwiek prawdopodobnie najlepszym do obliczania ręcznie):

Ogólne rozwiązanie pierwszego równania to 3 + 4i
Znajdujemy najmniejsze takie i, że x = 3 + 4i spełnia drugie równanie:
3 (0), 7 (1), 11 (2), 15 (3), 19 (4).
Najmniejsze takie i to 4.
Z dwóch pierwszych równań otrzymujemy zatem kongruencję x ≡ 19 (mod 20).
Ogólne rozwiązanie dwóch pierwszych równań to 19 + (4 · 5)j.
Znajdujemy najmniejsze takie j, że x = 19 + 20j spełnia trzecie równanie:
19 (0), 39 (1), 59 (2), 79 (3), 99 (4).
Czyli najmniejsze rozwiązanie to 99, a ogólne 99 + (4 · 5 · 7)k.

Uogólnienie[edytuj kod]

Niech R będzie pierścieniem przemiennym z jedynką, a I1, I2, ..., In jego ideałami. Jeśli są one parami względnie pierwsze, tj.

,

to naturalny homomorfizm

zdefiniowany przez warstwy elementu względem ideałów

jest epimorfizmem.

Wersja dla liczb wynika z zastosowania twierdzenia do pierścienia liczb całkowitych, będącego pierścieniem ideałów głównych.

Przypisy

Bibliografia[edytuj kod]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.
  • Donald Knuth: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, 1997.