Chińskie twierdzenie o resztach

Z Wikipedii

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 $y_1,y_2, \dots, y_k$ są dowolnymi liczbami całkowitymi, a $n_1, n_2, \dots, n_k$ to liczby parami względnie pierwsze)

spełnia dokładnie jedna liczba $x \in <1,n_1n_2n_3 \cdots n_k>$ .

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

[edytuj] Algorytm rozwiązywania układu kongruencji

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

Mianowicie, niech $M = n_1n_2\dots n_k$ oraz $M_i = \frac{M}{n_i}$ , wtedy na podstawie założenia $n i$ oraz $M i$ są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie $f_i,\ g_i \in \Z$ , że

f i n i + g i M i = 1

Niech $e i = g i M i$ . Wówczas $e_i \equiv 1\ (\bmod\ n_i)$ oraz $e_i \equiv 0\ (\bmod\ n_j)$ dla $j \ne i$ . 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$ .

[edytuj] Przykład

Mamy układ:

$x \equiv 3 \mod 4$

$x \equiv 4 \mod 5$

$x \equiv 1 \mod 7$

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

Ogólne rozwiązanie pierwszego równania to

3 + 4 i

Znajdujemy najmniejsze

i

, takie że

x = 3 + 4 i

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 $x \equiv 19 \mod 20$

Ogólne rozwiązanie dwóch pierwszych równań to $19 + (4 \times 5)j$

Znajdujemy najmniejsze

j

, takie że

x = 19 + 20 j

spełnia trzecie równanie:

19 (0), 39 (1), 59 (2), 79 (3), 99 (4)

Czyli najmniejsze rozwiązanie to

99

, a ogólne $x \equiv 99 \mod 4\times 5 \times 7$

Kategorie: Teoria liczb • Kryptologia

We provide Linux to the World

Chińskie twierdzenie o resztach

Z Wikipedii

[edytuj] Algorytm rozwiązywania układu kongruencji

[edytuj] Przykład

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach