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
Solve a system of integer congruences.
In [1]: a = [0, 3, 4] In [2]: m = [3, 4, 5] In [3]: x = galois.crt(a, m); x 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
Solve a system of polynomial congruences.
In [5]: GF = galois.GF(7) In [6]: x_truth = galois.Poly.Random(10, field=GF); x_truth Out[6]: Poly(x^10 + 2x^9 + 3x^8 + 6x^7 + 2x^6 + 6x^4 + 4x^3 + 3x^2 + 2x + 4, GF(7)) In [7]: m = [galois.irreducible_poly(7, 2), galois.irreducible_poly(7, 3), galois.irreducible_poly(7, 4)]; m Out[7]: [Poly(x^2 + 1, GF(7)), Poly(x^3 + 2, GF(7)), Poly(x^4 + x + 1, GF(7))] In [8]: a = [x_truth % mi for mi in m]; a Out[8]: [Poly(x, GF(7)), Poly(x^2 + 6x + 2, GF(7)), Poly(2x^2 + 2x + 6, GF(7))] In [9]: x = galois.crt(a, m); x Out[9]: Poly(2x^8 + x^7 + 2x^6 + 2x^5 + 4x^4 + 3x^3 + 4x^2 + 3x, GF(7)) In [10]: for i in range(len(a)): ....: ai = x % m[i] ....: print(f"{x} = {ai} (mod {m[i]}), Valid congruence: {ai == a[i]}") ....: Poly(2x^8 + x^7 + 2x^6 + 2x^5 + 4x^4 + 3x^3 + 4x^2 + 3x, GF(7)) = Poly(x, GF(7)) (mod Poly(x^2 + 1, GF(7))), Valid congruence: True Poly(2x^8 + x^7 + 2x^6 + 2x^5 + 4x^4 + 3x^3 + 4x^2 + 3x, GF(7)) = Poly(x^2 + 6x + 2, GF(7)) (mod Poly(x^3 + 2, GF(7))), Valid congruence: True Poly(2x^8 + x^7 + 2x^6 + 2x^5 + 4x^4 + 3x^3 + 4x^2 + 3x, GF(7)) = Poly(2x^2 + 2x + 6, GF(7)) (mod Poly(x^4 + x + 1, GF(7))), Valid congruence: True