Chińskie twierdzenie o resztach

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

x \equiv y_1\ (\bmod\ n_1),
x \equiv y_2\ (\bmod\ n_2),
...
x \equiv y_k\ (\bmod\ n_k),

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 \leqslant x \leqslant n_1\cdot n_2\cdot n_3\cdot \ldots \cdot n_k'[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 | edytuj kod]

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

Mianowicie, niech

M = n_1\cdot n_2\cdot n_3\cdot \ldots \cdot n_k

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

f_i n_i + g_i M_i = 1.

Niech ei = giMi (ik). Wówczas

e_i \equiv 1\ (\bmod\ n_i)

oraz

e_i \equiv 0\ (\bmod\ n_j)

gdy ji. Wtedy x zdefiniowany wzorem


x = \sum_{i=1}^{k} y_i e_i

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

Przykład[edytuj | edytuj kod]

Dany jest układ kongruencji:

x \equiv 3 \ (\bmod 4),
x \equiv 4 \ (\bmod 5),
x \equiv 1 \ (\bmod 7).

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 | 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.

I_i+I_j=R,\;(i\neq j,\,i,j\leqslant n),

to naturalny homomorfizm

\phi\colon R \rightarrow R/I_1 \times R/I_2 \times \cdots \times R/I_n

zdefiniowany przez warstwy elementu względem ideałów

\phi (a) = (a+I_1, a+I_2, \ldots, a+I_n)

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 | 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.