galois.crt¶

galois.crt(remainders, moduli)¶

Solves the simultaneous system of congruences for \(x\).

Parameters¶

remainders : Sequence[int] or Sequence[galois.Poly]¶

The integer or polynomial remainders \(a_i\).

moduli : Sequence[int] or Sequence[galois.Poly]¶

The integer or polynomial moduli \(m_i\).

Returns¶

The simultaneous solution \(x\) to the system of congruences.

Return type¶

int or galois.Poly

Notes

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}\]

References

• Section 14.5 from https://cacr.uwaterloo.ca/hac/about/chap14.pdf

Examples

Integers

Define a system of integer congruences.

In [1]: a = [0, 3, 4]

In [2]: m = [3, 4, 5]

Solve the system of congruences.

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

Show that the solution satisfies each congruence.

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

Polynomials

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

In [5]: GF = galois.GF(7)

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

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

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

Solve the system of congruences.

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

Show that the solution satisfies each congruence.

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