中国剩余定理--【信息安全】

这时上学期的信息安全学科的“公钥密码体制”中一章，关于数论基础的内容中说到的。

有题如下：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。

即：有一批物品，三个三个地数余二个，五个五个地数余三个，七个七个地数余二个，问这批物品最少有多少个。

这一题的解法也很简单：三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五使得知；

即将该数除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，加起来后除以105，取余就是答案。

即2 * 70 + 3 * 21 + 2 * 15 = 233，除以105取余，即为23。

至于上述的70，21，15是由初始数的个数3，5，7决定的；

因为70是5和7的公倍数，且除以3余1；

    21是3和7的公倍数，且除以5余1；

    15是3和5的公倍数，且除以7余1。

理解为程序即是：

#include <iostream>

using namespace std;

int CommonMult( int x,  int mul)  //满足条件的公倍数
{
    int ok = 0;
    int num = mul;
    while(0 == ok)
    {
        if((num - 1) % x == 0)
            ok = 1;
        else
            num += mul;
    }
    return num;
}

int Remain( int x,  int y,  int z,  int xr,  int yr,  int zr)  //分别三个数及其余数
{
    int x1 = y * z;  //寻找取余x为1的最小的公倍数
    int y1 = x * z;
    int z1 = x * y;
    x1 = CommonMult(x, x1);  //满足条件
    y1 = CommonMult(y, y1);
    z1 = CommonMult(z, z1);

    int sum = x1 * xr + y1 * yr + z1 * zr;  //求和
    sum = sum % (x * y * z);  //取余
    return sum;
}

int main()
{
    cout << Remain(3, 5, 7, 2, 3, 2) << endl;
    //cout << Remain(9, 7, 5, 6, 2, 3) << endl;  //
    //cout << Remain(2, 4, 5, 1, 1, 3) << endl;  //x,y,z非互质
    return 0;
}

上述x,y,z为三个为组数的个数，xr,yr,zr则分别为余数。

仅是按照解题思想完成，有诸多不完全之处还请各位大神指教...

o(∩_∩)o 

中国剩余定理--【信息安全】

原文：http://blog.csdn.net/xjm199/article/details/19767171