galois.crt¶

class galois.crt(a, m)¶

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

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

Parameters

a (array_like) – The integer remainders \(a_i\).
m (array_like) – The integer modulii \(m_i\).

Returns

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

Return type

int

Examples

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

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

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

In [475]: 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