Chinese Remainder Theorem demo

CRT_demo.py

#!/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()