6161619778

Chińskie twierdzenie o resztach (Chinese remainder tlieorem -CRT):

Jeżeli liczby całkowite n_t, n₂n_k są parami względnie pierwsze, to układ równań:

x =a_t (mod n_k) x =a₂ (mod n₂)

x sa_k (mod n_k)

ma jednoznaczne rozwiązanie w zbiorze ^ _n. gdzie n = n_In₂... n_k.

Algorytm Gaussa jest jednym ze skutecznych algorytmów rozwiązywania powyższego układu równań:

x = aiNiMi mod n

gdzie: N_t = n / n, i M, = JV,-'' mod iii, zaś złożoność obliczeniowa algorytmu: O ((log₂ nf).

Przykład:

x =J (mod 7) x = 7 (mod 13)

Rozwiązanie wg. algorytmu Gaussa:

n, = 7 n₂ = 13    n = 7 13 = 91

N, = 91/7 = 13    N₂ = 91/13 = 7

Mi = 13 '' mod 7 = 6'' mod 7 = 6 (klasa równoważności)

M₂ = 7~' mod 13 = 2

x = (3 13 6 + 7 7 2) mod 91 =(234 + 98) mod 91 =

332 mod 91 = 59 mod 91 = 59