RSA解密举例

解：
N= 1889570071
e1 = 1021763679
e2= 519424709
c1= 1244183534 and c2= 732959706
由题意得: c1 = m ^ e1 (mod N), c2 = m ^ e2 (mod N)
由扩展欧几里得算法得: e1·u + e2·v = gcd(e1,e2) = 1
c1^u · c2^v ≡ m^gcd(e1,e2) (mod N)
即是c1^u · c2^v ≡ m (mod N)
其中，c1^u · c2^v (mod N)
= (c1^u mod N · c2^v mod N) mod N
=m mod N
最后解得m

#include<iostream>
using namespace std;
typedef long long L;

L exgcd(L a, L b, L &x, L &y)//ax+by=1返回a,b的gcd，同时求的一组满足题目的最小正整数解    
{
    L ans, t;
    if (b == 0)
    { 
        x = 1; 
        y = 0; 
        return a; 
    }
    ans = exgcd(b, a%b, x, y); 
    t = x; 
    x = y; 
    y = t - (a / b)*y;
    return ans;
}

L expmod(L a, L b, L n)//快速幂求余算法a^b%n
{
    L res = 1;
    a %= n;
    while (b)
    {
        if (b & 1)//b是否为奇数
            res = (res * a) % n;
        a = (a * a) % n;
        b /= 2;
    }
    return res;
}

void main()
{
    L n = 1889570071;
    L e1 = 1021763679;
    L e2 = 519424709;
    L c1 = 1244183534;
    L c2 = 732959706;
    L m, u, v, t, t1, t2, t3;
    exgcd(e1, e2, u, v);
    cout << u << endl << v << endl;
    t1 = expmod(c1, u, n);
    t2 = expmod(c2, v, n);
    t3 = t1 * t2;
    t = expmod(t3, 1, n);
    m = t;
    cout << m << endl;  
}