#include <iostream>
using namespace std;

// 快速幂：计算 a 的 b 次方再对 m 取余
long long fast_pow(long long a, long long b, long long m) {
    long long res = 1 % m;      // 结果，至少是1（如果m=1，则结果为0）
    a %= m;                     // 先把底数缩小
    while (b > 0) {
        if (b & 1) res = (res * a) % m;  // 如果当前二进制位为1，乘一次
        a = (a * a) % m;                // 底数平方
        b >>= 1;                        // 指数右移一位（除以2）
    }
    return res;
}

// 求逆元：找一个数 x，使得 a*x ≡ 1 (mod m)
// 这里简单用暴力枚举（仅适用于小数字教学演示）
long long mod_inverse(long long a, long long m) {
    a = a % m;
    for (long long i = 1; i < m; i++) {
        if ((a * i) % m == 1)
            return i;
    }
    return -1; // 不存在（正常情况下不会发生）
}

// 使用 CRT 加速的 RSA 解密
// 输入：密文 c，素数 p，素数 q，预计算的 dp，dq，qinv
long long rsa_decrypt_crt(long long c, long long p, long long q,
                          long long dp, long long dq, long long qinv) {
    // 1. 计算 m1 = c^{dp} mod p
    long long m1 = fast_pow(c, dp, p);
    // 2. 计算 m2 = c^{dq} mod q
    long long m2 = fast_pow(c, dq, q);
    // 3. 合并：计算差并确保为非负数
    long long diff = (m1 - m2) % p;
    if (diff < 0) diff += p;          // C++ 中 % 可能为负，转成正数
    long long h = (qinv * diff) % p;
    long long m = m2 + h * q;         // 最终解密结果
    return m;
}

int main() {
    // 设置小素数方便演示（实际中都是几百位的）
    long long p = 3, q = 11;          // 两个素数
    long long n = p * q;              // 模数 n = 33
    long long phi = (p-1) * (q-1);    // 欧拉函数 φ(n) = 20
    long long e = 7, d = 3;           // 公钥指数 e，私钥指数 d (7*3=21≡1 mod 20)

    // 明文（要加密的数字）
    long long m_original = 5;         // 明文设为5

    // 加密：计算 c = m^e mod n
    long long c = fast_pow(m_original, e, n);  // 得到密文14
    cout << "密文: " << c << endl;

    // 普通解密：直接计算 c^d mod n
    long long m_normal = fast_pow(c, d, n);
    cout << "普通解密结果: " << m_normal << endl;  // 应该等于5

    // CRT 加速解密所需的预计算参数
    long long dp = d % (p - 1);           // dp = 3 % 2 = 1
    long long dq = d % (q - 1);           // dq = 3 % 10 = 3
    long long qinv = mod_inverse(q, p);   // q=11对模p=3的逆元，因为11%3=2，2的逆元是2

    cout << "dp=" << dp << ", dq=" << dq << ", qinv=" << qinv << endl;

    // 使用CRT解密
    long long m_crt = rsa_decrypt_crt(c, p, q, dp, dq, qinv);
    cout << "CRT解密结果: " << m_crt << endl;  // 应该也是5

    // 注意：实际RSA中数字长度成百上千位，但原理一模一样
    return 0;
}

def fast_pow(a, b, m):
    """快速幂：计算 a^b mod m"""
    res = 1 % m
    a %= m
    while b:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res

def mod_inverse(a, m):
    """求逆元（暴力枚举，仅教学用）"""
    a %= m
    for i in range(1, m):
        if (a * i) % m == 1:
            return i
    return None

def rsa_decrypt_crt(c, p, q, dp, dq, qinv):
    """使用CRT加速RSA解密"""
    m1 = fast_pow(c, dp, p)          # c^{dp} mod p
    m2 = fast_pow(c, dq, q)          # c^{dq} mod q
    h = (qinv * (m1 - m2)) % p       # Python % 自动得到正数
    m = m2 + h * q
    return m

if __name__ == "__main__":
    # 小素数例子
    p, q = 3, 11                     # 两个素数
    n = p * q                        # 模数 33
    phi = (p-1) * (q-1)              # 欧拉函数 20
    e, d = 7, 3                      # 公钥指数、私钥指数

    m_original = 5                   # 明文
    c = fast_pow(m_original, e, n)   # 加密得密文14
    print(f"密文: {c}")

    m_normal = fast_pow(c, d, n)     # 普通解密
    print(f"普通解密结果: {m_normal}")

    # 预计算CRT参数
    dp = d % (p - 1)                 # dp = 1
    dq = d % (q - 1)                 # dq = 3
    qinv = mod_inverse(q, p)         # qinv = 2 (因为11%3=2, 2*2=4≡1)
    print(f"dp={dp}, dq={dq}, qinv={qinv}")

    m_crt = rsa_decrypt_crt(c, p, q, dp, dq, qinv)
    print(f"CRT解密结果: {m_crt}")   # 输出5，和明文一样