什么是中国剩余定理?
它来源一个“物不知数”问题。即“有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?”。为了求解,我们列如下方程
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。当然,说是这样解的并不严谨,因为它并未经过任何事实验证,然而博主没有构造实例的条件,因此这种方法的正确性值得讨论——至少有实际例子证明。