中国剩余定理（CRT）

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之 剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”

具体解法
①找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
②用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
③用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数

中国剩余定理的公式

图片.png

当m互质时，python实现代码

from Crypto.Util.number import long_to_bytes
from functools import reduce
from gmpy2 import gcd,invert
Num=3
m = [ ?, ?, ?]
a = [ ?, ?, ?]
M=reduce(lambda x,y: x*y, m)
Mi=[M/i for i in m]
t=[invert(Mi[i], m[i]) for i in range(Num)]
x=0
for i in range(Num):
      x+=a[i]*t[i]*Mi[i]
print(long_to_bytes(x%M))

当m不互质时，python实现代码

import hashlib
from functools import reduce
from gmpy2 import gcd
from Crypto.Util.number import *

Num=?
m = [???,???,???]
a = [???,???,???]
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 china(num):
      m1,a1,lcm=m[0],a[0],m[0]
      for i in range(1,num):
            m2=m[i]
            a2=a[i]
            c=a2-a1
            g,k1,k2=egcd(m1,m2)
            lcm=lcm*m[i]//gcd(lcm,m[i])
            if c%g :
                  print('No Answer!')
                  return 0
            x0=c//g*k1
            t=m2//g
            x0=(x0%t+t)%t
            a1+=m1*x0
            m1=m2//g*m1
      return a1
ans=china(Num)
i=0
x=ans+i*gbs