中国剩余定理（CRT），学公钥加密的时候刚学过，但是没想起来……

简单说来是这样的：
假设m_1到m_k为两两互素的，M = m_1*m_2*...*m_k,则对于比M小的任意整数A，都对应着一个k元组
(a_1,...a_k),其中a_i = A%m_i。其中A与这样的k元组是一一对应关系。

其中，从A到k元组的转换是显然可以惟一确定的，只要a_i = A mod m_i即可，反之
对给定的一个k元组，可以用如下方式计算A：

定义M_i = M/m_i，则对所有不为i的j来说

M_i ≡ 0(mod m_j);因为M_i可以被m_j整除。
令c_i = M_i * (M_ir mod m_i)，其中M_ir是M_i相对于m_i的逆元。用扩展欧几里德算法可以得到。

则 A ≡ sum(a_i*c_i) mod M。

要证明A是正确的，则要证明 a_i ≡ A mod m_i。因为c_j ≡ M_j ≡ 0 mod m_i,而且c_i ≡ 1 mod m_i,故a_i = A mod m_i。

在本题中，我们知道m_i = {23，28，33}，且它们两两互素。并且已知a_i分别为p,e,i，让我们去求A。

则按上面的步骤求即可。


以上是个人理解，如果有不对的请指正……

• Re:中国剩余定理 (5) robey 2010-06-18 21:44:22