Chińskie twierdzenie o resztach
Z Wikipedii
Chińskie twierdzenie o resztach mówi, że układ kongruencji:
- ...
- (gdzie
są dowolnymi liczbami całkowitymi, a 
to liczby parami względnie pierwsze)
spełnia dokładnie jedna liczba 
.
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 
oraz 
, wtedy na podstawie założenia ni oraz Mi są względnie pierwsze, tzn. korzystając z rozszerzonego algorytmu Euklidesa istnieją takie 
, że
Niech ei = giMi. Wówczas 
oraz 
dla 
. Wtedy x zdefiniowany wzorem
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:
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 + 4i
- Znajdujemy najmniejsze i, takie ż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
- Ogólne rozwiązanie dwóch pierwszych równań to
- Znajdujemy najmniejsze j, takie ż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
