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 [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]: rng = np.random.default_rng(572186432)

In [7]: a = [galois.Poly.Random(2, seed=rng, field=GF), galois.Poly.Random(3, seed=rng, field=GF), galois.Poly.Random(4, seed=rng, field=GF)]; a
Out[7]: 
[Poly(3x^2 + 6x + 3, GF(7)),
 Poly(5x^3 + 4x^2 + 4x, GF(7)),
 Poly(3x^4 + 6x^3 + 2x^2 + 6x + 5, GF(7))]

In [8]: m = [galois.Poly.Random(3, seed=rng, field=GF), galois.Poly.Random(4, seed=rng, field=GF), galois.Poly.Random(5, seed=rng, field=GF)]; m
Out[8]: 
[Poly(3x^3 + 6x^2 + 2x, GF(7)),
 Poly(5x^4 + 6x^3 + 4x^2 + 6x + 2, GF(7)),
 Poly(6x^5 + x^4 + x^3 + 3x^2 + 1, GF(7))]

In [9]: x = galois.crt(a, m); x
Out[9]: Poly(5x^11 + x^10 + 2x^8 + 3x^7 + 5x^5 + 4x^4 + 4x^3 + x + 3, 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(5x^11 + x^10 + 2x^8 + 3x^7 + 5x^5 + 4x^4 + 4x^3 + x + 3, GF(7)) = Poly(3x^2 + 6x + 3, GF(7)) (mod Poly(3x^3 + 6x^2 + 2x, GF(7))), Valid congruence: True
Poly(5x^11 + x^10 + 2x^8 + 3x^7 + 5x^5 + 4x^4 + 4x^3 + x + 3, GF(7)) = Poly(5x^3 + 4x^2 + 4x, GF(7)) (mod Poly(5x^4 + 6x^3 + 4x^2 + 6x + 2, GF(7))), Valid congruence: True
Poly(5x^11 + x^10 + 2x^8 + 3x^7 + 5x^5 + 4x^4 + 4x^3 + x + 3, GF(7)) = Poly(3x^4 + 6x^3 + 2x^2 + 6x + 5, GF(7)) (mod Poly(6x^5 + x^4 + x^3 + 3x^2 + 1, GF(7))), Valid congruence: True