中国剩余定理

本文最后更新于 <span id="expire-date"></span> 天前，文中部分描述可能已经过时。

验证中国剩余定理

如题

三个方程组成的一次同余方程组

顺序是a1，a2，a3，m1，m2，m3

每个数字之间是通过换行来分割的

数字大小最大设值为500位

需要判断m值是否能运用一次同余方程。

题解

import sys
with open('C:\\Users\\吴文之\\Desktop\\20个数据\\19.txt') as file_object:
    lines = file_object.readlines()


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


# 利用欧几里得算法判断两个数的最大公约数是否为1，即是否互素
def modreverse(c, d):
    if gcd(c, d) != 1:
        return None
    u1, u2, u3 = 1, 0, c
    v1, v2, v3 = 0, 1, d
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % d


a1 = int(lines[0])
a2 = int(lines[1])
a3 = int(lines[2])
m1 = int(lines[3])
m2 = int(lines[4])
m3 = int(lines[5])
# 读取txt文件中的a1,a2,a3,m1,m2,m3
mark = True
if gcd(m1, m2) != 1 | gcd(m1, m3) != 1 | gcd(m2, m3) != 1:
    sys.exit(-1)
if gcd(m1, m2) != 1:
    print("m1和m2两两不互素，不符合条件")
    sys.exit(-1)
if gcd(m1, m3) != 1:
    print("m1和m3两两不互素，不符合条件")
    sys.exit(-1)
if gcd(m2, m3) != 1:
    print("m2和m3两两不互素，不符合条件")
    sys.exit(-1)
    # 测试是否符合条件
if mark == True:
    M = m1 * m2 * m3
    M1 = m2 * m3
    M2 = m1 * m3
    M3 = m1 * m2
    M1_ = modreverse(M1, m1)
    print("M1的模逆为" + str(M1_))
    M2_ = modreverse(M2, m2)
    print("M2的模逆为" + str(M2_))
    M3_ = modreverse(M3, m3)
    print("M3的模逆为" + str(M3_))

    x = (a1 * M1_ * M1 + a2 * M2_ * M2 + a3 * M3_ * M3) % M
    print("\nx="+str(a1 * M1_ * M1 + a2 * M2_ * M2 + a3 * M3_ * M3)+"\n(mod"+str(M)+")\n="+str(x))
else:
    print("x无解")

本文作者：Mosquito

本文链接： http://example.com/2022/01/26/%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86/

Mosquito 天使之吻手打

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。

更新于 2022-05-22

# 密码学 # 初等数论