什么是中国剩余定理？
它来源一个“物不知数”问题。即“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”。为了求解，我们列如下方程
x=2%3 x=3%5 x=2%7
按照博主普通人的思维，会先按最大的那个进行套，例如x=2%7有解9,16,23,30...然后再套前面两个式子，发现最小的x=23，通解是x=23+k*3*5*7。数小的时候当然简单，但数大起来就完全不能这么做了。
我们再看看古人怎么解的：
”三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知“
即 70*2+21*3+15*2 = 233=105*2+23
如何求解普遍性”物不知数“问题？
显然这种方法似乎要简单一点。可惜的是只能应对3，5，7这种问题，下面我们来看普遍性解法：
假设有n个这样的方程 x=a1%m1 x=a2%m2 x=a3%m3 ... x=an%mn 解: 设M=m1*m2*m3*...*mn Mi-1=M/mi ti=Mi-1 %mi 那么x=a1t1M1+a2t2M2+...+antnMn+kM k∈0,1,2,3,4,...
如何攻击RSA加密算法？
已知有三个用户，他们使用不同的公钥对消息M进行加密，生成密文C0,C1,C2。
我们列出一元同余线性方程组如下
Me0=C0%N0 Me1=C1%N1 Me2=C2%N2
再根据中国剩余定理，我们可以求得一个Mx满足条件，再通过因式分解，我们就能求得明文消息M。当然，说是这样解的并不严谨，因为它并未经过任何事实验证，然而博主没有构造实例的条件，因此这种方法的正确性值得讨论——至少有实际例子证明。
