中国剩余定理是什么的方法：从《孙子算经》到现代密码学的深度解析

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a)  y, y
def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return (x % m + m) % m
def chinese_remainder_theorem(pairs):
    """
    pairs: list of tuples (remainder, modulus)
    Example: [(2, 3), (3, 5), (2, 7)]
    """
    moduli = [p[1] for p in pairs]
    remainders = [p[0] for p in pairs]
    M = 1
    for m in moduli:
        M = m
    x = 0
    for i in range(len(pairs)):
        M_i = M // moduli[i]
        t_i = modinv(M_i, moduli[i])
        x += remainders[i]  M_i  t_i
    return x % M
测试
pairs = [(2, 3), (3, 5), (2, 7)]
print("解为:", chinese_remainder_theorem(pairs))
                

#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b  x;
    return d;
}
ll crt(const vector& a, const vector& m) {
    ll M = 1;
    for (ll mi : m) M = mi;
    ll x = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        ll Mi = M / m[i];
        ll xi, yi;
        extgcd(Mi, m[i], xi, yi);
        x = (x + a[i]  Mi % M  xi % M) % M;
    }
    return (x + M) % M;
}
int main() {
    vector a = {2, 3, 2}; // 余数
    vector m = {3, 5, 7}; // 模数
    cout << "解为: " << crt(a, m) << endl;
    return 0;
}