# Implementation of Chinese Remainder Theorem

Contents

## 模数两两互素时

  1 2 3 4 5 6 7 8 9 10 11  from Crypto.Util.number import inverse from functools import reduce def crt(a, m): '''Return a solution to a Chinese Remainder Theorem problem. ''' M = reduce(lambda x, y: x*y, m) Mi = [M//i for i in m] t = [inverse(Mi[i], m[i]) for i in range(len(m))] x = sum([a[i]*t[i]*Mi[i] for i in range(len(m))]) return x % M 

## 不满足模数两两互素时

x 为最小解，m1 , m2 , … , mn 的最小公倍数为 L ，X < M ，易知 X = x + k * L ，枚举 k 就可以了。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  from Crypto.Util.number import GCD, inverse from functools import reduce def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def crt_minial(a, m): '''Return the minial solution to a Chinese Remainder Theorem problem. ''' assert len(a) == len(m), f"length of {a} is not equal to {b}" m1, a1, lcm = m[0], a[0], m[0] for i in range(1, len(m)): c = a[i]-a1 g, k, _ = egcd(m1, m[i]) lcm = lcm*m[i]//GCD(lcm, m[i]) assert c % g == 0, 'No Answer!' t = m[i]//g a1 += m1*(((c//g*k) % t + t) % t) m1 = m[i]//g*m1 return a1