Chińskie twierdzenie o resztach

397 jpg' alt='Chi%C5%84skie_twierdzenie_o_resztach'>
Chińskie twierdzenie o resztach mówi, że układ kongruencji:spełnia dokładnie jedna liczba .Jest to jedno z najważniejszych twierdzeń w teorii liczb i kryptografii.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 , żeNiech ei = giMi. Wówczas oraz dla . Wtedy x zdefiniowany wzoremspełnia powyższy układ kongruencji, jest to jedno z rozwiazań - pozostałe różnią się o wielokrotność M.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):