526互联

CINTA hw6

发布时间 2023-12-06 00:50:40作者: Sophiawxr

1. 运用CRT求解：

\[x ≡ 8 ( mod 11 ) \]

\[x ≡ 3 ( mod 19 ) \]

解：
记 a = 8, b = 3, p = 11, q = 19
n=pq=209
egcd算法求解p-1和q-1
使pp-1≡1(mod q) , qq-1≡1(mod p)
得p-1= 7 , q-1= 7
令y≡aqq-1+bpp-1(mod n),y= 41
验证得y为正确解。

2. 运用CRT求解

\[x ≡ 1 ( mod 5 ) \]

\[x ≡ 2 ( mod 7 ) \]

\[x ≡ 3 ( mod 9 ) \]

\[x ≡ 4 ( mod 11 ) \]

解：
记 a1= 1, a2 = 2, a3=3 , a4= 4
m1 = 5, m2 = 7 , m3 = 9 , m4 = 11
n=m1·m2·m3·m4=3465
egcd算法求解m1~m4逆元
使mimi-1≡1(mod q)
得m1-1= 7 , m2-1= 7,m3= 7 , m4-1= 7
令y≡a1m1m1-1+a2m2m2-1+a3m3m3-1+a4m4m4-1(mod n)
得y=1731
验证得y为正确解。

3. 手动计算20002019(mod 221),不允许使用电脑或其他电子设备。【提示：这是一道看上去与中国剩余定理无关的计算题】

解：
221=13 * 17

20002019( mod 13)
≡ ( 200013 )15520004( mod 13 )
≡ 1155 * 5( mod 13 )
≡5 ( mod 13 )

20002019( mod 17)
≡ ( 200016 )12620003（mod 17）
≡ 1 126 5( mod 17 )
≡ 5( mod 17)

得：

\[x ≡ 5 ( mod 13 ) \]

\[x ≡ 5 ( mod 17 ) \]

记 a = 5, b = 5, p = 13, q = 17
n=pq=221
egcd算法求解p-1和q-1
使pp-1≡1(mod q) , qq-1≡1(mod p)
得p-1= 4 , q-1= 10
令y≡aqq-1+bpp-1(mod n)
y= 5
验证得y为正确解。

7. 实现一个利用CRT求解同余方程的程序（python或c语言都可以）

点击查看代码 


#include <iostream>
#include <vector>

// 扩展的欧几里得算法，计算 a 模 m 的乘法逆元
int mod_inverse(int a, int m) {
    int m0 = m;
    int y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        int q = a / m;
        int t = m;

        m = a % m;
        a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

// 使用中国剩余定理求解同余方程组
int solve_congruences(const std::vector<std::pair<int, int>>& congruences) {
    int result = 0;
    int product = 1;

    for (const auto& congruence : congruences) {
        product *= congruence.second;
    }

    for (const auto& congruence : congruences) {
        int ai = congruence.first;
        int mi = congruence.second;
        int bi = product / mi; // product 除以 mi
        int bi_inverse = mod_inverse(bi, mi); // bi 的乘法逆元

        result += ai * bi * bi_inverse;
    }

    return result % product;
}

int main() {
    int num_equations;

    // 输入同余方程的数量
    std::cout << "输入同余方程的数量: ";
    std::cin >> num_equations;

    std::vector<std::pair<int, int>> congruences;

    // 输入同余方程
    for (int i = 0; i < num_equations; ++i) {
        int ai, mi;
        std::cout << "输入余数" << i + 1 << ": ";
        std::cin >> ai;
        std::cout << "输入模数" << i + 1 << ": ";
        std::cin >> mi;

        congruences.push_back({ ai, mi });
    }

    // 使用中国剩余定理求解同余方程组
    int solution = solve_congruences(congruences);

    // 输出结果
    std::cout << "The solution is: " << solution << std::endl;

    return 0;
}

</details>

运行结果：

image