galois.crt¶
- galois.crt(remainders, moduli)¶
Solves the simultaneous system of congruences for \(x\).
- Parameters
- Returns
The simultaneous solution \(x\) to the system of congruences.
- Return type
Notes
This function implements the Chinese Remainder Theorem.
\[ \begin{align}\begin{aligned}x &\equiv a_1\ (\textrm{mod}\ m_1)\\x &\equiv a_2\ (\textrm{mod}\ m_2)\\x &\equiv \ldots\\x &\equiv a_n\ (\textrm{mod}\ m_n)\end{aligned}\end{align} \]References
Section 14.5 from https://cacr.uwaterloo.ca/hac/about/chap14.pdf
Examples
In [1]: a = [0, 3, 4] In [2]: m = [3, 4, 5] In [3]: x = galois.crt(a, m); x 1 -1 1 1 -2 5 Out[3]: 39 In [4]: for i in range(len(a)): ...: ai = x % m[i] ...: print(f"{x} = {ai} (mod {m[i]}), Valid congruence: {ai == a[i]}") ...: 39 = 0 (mod 3), Valid congruence: True 39 = 3 (mod 4), Valid congruence: True 39 = 4 (mod 5), Valid congruence: True