# galois.crt¶

galois.crt(remainders, moduli)

Solves the simultaneous system of congruences for $$x$$.

Parameters
• remainders (tuple, list) – The integer or polynomial remainders $$a_i$$.

• moduli (tuple, list) – The integer or polynomial moduli $$m_i$$.

Returns

The simultaneous solution $$x$$ to the system of congruences.

Return type

int

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

Examples

Solve a system of integer congruences.

In : a = [0, 3, 4]

In : m = [3, 4, 5]

In : x = galois.crt(a, m); x
Out: 39

In : 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 : GF = galois.GF(7)

In : x_truth = galois.Poly.Random(10, field=GF); x_truth
Out: Poly(x^10 + 2x^9 + 5x^8 + 4x^7 + 3x^6 + 5x^5 + 2x^4 + 5x^3 + 6x^2 + 6, GF(7))

In : m = [galois.irreducible_poly(7, 2), galois.irreducible_poly(7, 3), galois.irreducible_poly(7, 4)]; m
Out: [Poly(x^2 + 1, GF(7)), Poly(x^3 + 2, GF(7)), Poly(x^4 + x + 1, GF(7))]

In : a = [x_truth % mi for mi in m]; a
Out:
[Poly(5x + 3, GF(7)),
Poly(2x^2 + 4x + 6, GF(7)),
Poly(2x^3 + x^2 + x + 5, GF(7))]

In : x = galois.crt(a, m); x
Out: Poly(4x^8 + 6x^7 + 3x^6 + 4x^3 + x + 2, GF(7))

In : for i in range(len(a)):
....:     ai = x % m[i]
....:     print(f"{x} = {ai} (mod {m[i]}), Valid congruence: {ai == a[i]}")
....:
Poly(4x^8 + 6x^7 + 3x^6 + 4x^3 + x + 2, GF(7)) = Poly(5x + 3, GF(7)) (mod Poly(x^2 + 1, GF(7))), Valid congruence: True
Poly(4x^8 + 6x^7 + 3x^6 + 4x^3 + x + 2, GF(7)) = Poly(2x^2 + 4x + 6, GF(7)) (mod Poly(x^3 + 2, GF(7))), Valid congruence: True
Poly(4x^8 + 6x^7 + 3x^6 + 4x^3 + x + 2, GF(7)) = Poly(2x^3 + x^2 + x + 5, GF(7)) (mod Poly(x^4 + x + 1, GF(7))), Valid congruence: True