galois.crt(moduli: ) int
galois.crt(moduli: ) Poly

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

Parameters:
remainders:
remainders:

The integer or polynomial remainders $$a_i$$.

moduli:
moduli:

The integer or polynomial moduli $$m_i$$.

Returns:

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

This function implements the Chinese Remainder Theorem.

$\begin{split}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{split}$

Examples

Define a system of integer congruences.

In : a = [0, 3, 4]

In : m = [3, 4, 5]


Solve the system of congruences.

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


Show that the solution satisfies each congruence.

In : for i in range(len(a)):
...:     ai = x % m[i]
...:     print(ai, ai == a[i])
...:
0 True
3 True
4 True


Define a system of polynomial congruences over $$\mathrm{GF}(7)$$.

In : GF = galois.GF(7)

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

In : m3 = galois.Poly.Random(3, field=GF)

In : m4 = galois.Poly.Random(4, field=GF)

In : m5 = galois.Poly.Random(5, field=GF)

In : m = [m3, m4, m5]; m
Out:
[Poly(6x^3 + 3x + 6, GF(7)),
Poly(3x^4 + 5x^3 + 4x^2 + 6x, GF(7)),
Poly(x^5 + x^4 + 4x^3 + 4x^2 + 6x + 3, GF(7))]

In : a = [x_truth % m3, x_truth % m4, x_truth % m5]; a
Out:
[Poly(3x^2 + x + 4, GF(7)),
Poly(2x^3 + 4x^2 + 5x + 1, GF(7)),
Poly(2x^4 + x^3 + 2x^2 + x + 3, GF(7))]


Solve the system of congruences.

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


Show that the solution satisfies each congruence.

In : for i in range(len(a)):
....:     ai = x % m[i]
....:     print(ai, ai == a[i])
....:
3x^2 + x + 4 True
2x^3 + 4x^2 + 5x + 1 True
2x^4 + x^3 + 2x^2 + x + 3 True