中国余下定理以及拉格朗日插值
********************************
鉴于在博客中写公式略显难看，有碍观瞻，博客中的内容我都事先用latex写了一个pdf的文档，可以在下链接下载
http://download.****.net/detail/xue_haiyang/7640513
下面所写的难免有各种错误，还请留言批评指正（欢迎任意的批评交流）
下步计划：1，RSA-OAEP 2，素数检测
********************************
《孙子算经》中，记载这样一个问题： “今有物不知其数，三三数之剩二，五五数之剩三，
七七数之剩二，问物几何。”用现在的话来说就是：“有一批物品，3个3个地数余2个，5个5个地数余3个，7个7个地数余2个，问这批物品最少有多少个?” 这是数论上的一个一元线性同余方程组问题，而中国剩余定理正是为了解决这样的问题。我这里并不是试图给出中国剩余定理的严格证明，而是从一个比较好理解的角度来分析下中国剩余定理，
中国剩余定理
回忆上节的中国剩余定理是说
对于互素的数, 和
, 并且知道
, 如果记
, 则
为了好理解，我先分析三个方程的问题，也就是给定
求? 我们看看
是不是
?
如果记
并且,
,
,
则有下面
其中每一列代表模第一个元素的值. 可见对于,
是
为了进一步看清楚中国剩余定理，或者更傻的直观看中国剩余定理
我们看下下面的问题
如果记
并且,
,
,
则有下面
则,
图形展示
下面看看图形吧对于问题
可以下面的图形蓝色线是模5为2的，红色线是模3为1的，那么蓝红重合的一点正是要求的7.
三个才过瘾，看看三个的图形
可以下面的图形蓝色线是模5为2的，红色线是模3为1的，三角折线和坐标的交点是模2为0的，那么蓝红和交点的重合的一点正是要求的22.
能不能从坐标的角度看这个问题的,
可以下面的图形蓝色线是模5为2的，红色线是模3为1的，中间的线是$x=y$这条线，那么蓝红重合的一点正是要求的7.
下面的问题呢？,
可以下面的图形蓝色线是模5为2的，红色线是模3为1的，中间的这条线是模15意义下的$y=2x$, 那么蓝红重合的一点正是要求的7.
站高点看
好了，下面从高一点的高度看中国剩余问题实际上这是在考虑整数环的同构定理
插值公式
下面看看传说中的拉格朗日差值公式。实际上这个同中国剩余定理一样是一个交换环上的同构定理，只不过这个是在多项式环上而已.
我们考虑一个二次多项式, 给定三对点
求多项式的问题。
令,
,
,
,
,
,