Created
December 16, 2016 10:50
-
-
Save PM2Ring/10ec06913b9266ebf736f7db6bee43b3 to your computer and use it in GitHub Desktop.
Chinese Remainder Theorem demo
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
''' Solve systems of simultaneous linear congruences using the Chinese Remainder Theorem | |
Chinese Remainder Theorem: | |
If X = r_i mod m_i for i in 1..n, m_i pairwise coprime | |
Let | |
M_i = M // m_i, y_i = M_i^(-1) mod m_i, i.e., y_i * M_i = 1 mod m_i | |
Then | |
y_i * M_i = 0 mod m_j for j != i | |
And therefore | |
X = sum(r_i * M_i * y_i mod M) | |
Written by PM 2Ring 2015.11.09 | |
Python 3 version 2016.12.16 | |
''' | |
from __future__ import print_function | |
from functools import reduce | |
#From Chinese Remainder Theorem Based Single and Multi-group | |
#Key Management Protocols by Xinliang Zheng | |
#https://books.google.com.au/books?id=BbWuczr-7SAC | |
def mod_inverse(b, m): | |
''' Find y: b*y % m = 1 ''' | |
m0 = m | |
q, r = m0 // b, m0 % b | |
y0, y = 0, 1 | |
while r: | |
y0, y = y, (y0 - q*y) % m | |
m0, b = b, r | |
q, r = m0 // b, m0 % b | |
return y | |
#Chinese Remainder Theorem | |
def crt(pairs): | |
''' Solve systems of linear congruences | |
using the Chinese Remainder Theorem | |
''' | |
mods, rems = zip(*pairs) | |
mprod = reduce(int.__mul__, mods, 1) | |
cmods = [mprod // m for m in mods] | |
imods = [mod_inverse(c, m) for c, m in zip(cmods, mods)] | |
a = [y * c for y, c in zip(imods, cmods)] | |
return mprod, sum(r * u % mprod for r, u in zip(rems, a)) % mprod | |
def main(): | |
# (modulus, remainder) pairs. Moduli should be pairwise coprime. | |
pairs = [(2, 1), (9, 8), (5, 4), (7, 3), (11, 5), (13, 6)] | |
mprod, x = crt(pairs) | |
print('{} mod {}'.format(x, mprod)) | |
print(all(x % m == r for m, r in pairs)) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment