The Chinese remainder theorem

The theorem

x = a1 (mod n1)
...
x = ak (mod nk)

The proof

x = a1 (mod n1)
x = a2 (mod n2)
y = a1 * q * n2 + a2 * p * n1  (mod N)
y = sum(ai * (N / ni) * invmod(N / ni, ni)
z = y (mod N)

Algorithm 1: Gauss algorithm

def ChineseRemainderGauss(n, N, a):
result = 0
for i in range(len(n)):
ai = a[i]
ni = n[i]
bi = N // ni
result += ai * bi * invmod(bi, ni) return result % N

Algorithm 2: Euclid

x = sum(ai * b * (N / ni))  for i=1...k
def ChineseRemainderEuclid(n, N, a):
result = 0
for i in range(len(n)):
ai = a[i]
ni = n[i]
_, _, si = ExtendedEuclid(ni, N // ni)
result += ai * si * (N // ni)
return LeastPositiveEquivalent(result, N)

The extended Euclidean algorithm

a * x + b * y = gcd(a, b)
x = qy + r
x = q1 * y + r1
q1 = q2 * r + r2
...
gcd(102, 38)102 = 2*38 + 26
38 = 1*26 + 12
26 = 2*12 + 2
12 = 6*2 + 0
2 = 26 - 2*12
2 = 26 - 2*(38 - 1*26) = 26 - 2*(38 - 1*(102 - 2*38))
2 = 3*102 - 8*38
def ExtendedEuclid(x, y):
x0, x1, y0, y1 = 1, 0, 0, 1
while y > 0:
q, x, y = math.floor(x / y), y, x % y
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return a, x0, y0 # gcd and the two coefficients

The modular inverse

17*x = 1 (mod 43)
Forward:
43 = 17*2 + 9
17 = 9*1 + 8
9 = 8*1 + 1 # <-- my GCD is here, so it is 1
Backward:
1 = 9 - 8*1
8 = 17 - 9*1
9 = 43 - 17*2
Replacing the first "backward" equation with everything else:
1 = 43 - 17*2 - 17 + 43 - 17*2 = 2*43 - 17*5
2*43 - 5*17 = 1 (mod 43)
-5*17 = 1 (mod 43)
def invmod(a, m):
g, x, y = ExtendedEuclid(a, m)
if g != 1:
raise ValueError('modular inverse does not exist')
else:
return x % m

References

--

--

--

Random lady whose eyes sparkle for science, and who loves writing. I plan to write about a large variety of interesting science topics, one bit at a time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to run Headless Chrome in scale

Headless Chrome

Bitrise- Flavor Wise Workflow for Flutter Integration Part-2

Building flexible Make targets

Hadoop Job Roles & Benefits — Latest updated (2020)

Introducing REN, BAO, PERP, LINA & BADGER futures trading on FMX

How to become SAFe Program Consultant (SPC)

The First Quarter Contributors Selection

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Astarte Kraus

Astarte Kraus

Random lady whose eyes sparkle for science, and who loves writing. I plan to write about a large variety of interesting science topics, one bit at a time.

More from Medium

4 Ways to Solve Linear Programming in Python

You’ll Never Look at the Bias-Variance Tradeoff the Same Way Again!

Calculus — Curves

Faster math typesetting in Jupyter and Python (Part 3)