中国剩余定理

python处理大数和数论的孙子算法实现

#  by EotStxTaB.H
#  on Sunday.20.11.1

import math 

def exgcd(a, b):
    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = a, b
    if b == 0:
        return 1, 0, a
    else:
        while r != 0:
            q = old_r // r
            old_r, r = r, old_r - q * r
            old_s, s = s, old_s - q * s
            old_t, t = t, old_t - q * t
    return old_s


def MjrCal(Mj, mj):
    s = exgcd(Mj, mj)
    while s < 1:
        s += mj
    return s


def solCal(fileNum):
    fileName = "C:/Users/15568/Desktop/study plus/密码实验/e2/20个数据/{}.txt".format(fileNum)
    number = 0
    with open(fileName) as file:
        lst = []
        for line in file.readlines():
            lst.append(int(line))
            number += 1
    number = number // 2
    a = lst[:number]
    mj = lst[number:]

    flag = True

    for i in range(number - 1):
        for j in range(i + 1, number):
            g = math.gcd(mj[i], mj[j])
            if g != 1:
                flag = False
                break
        else:
            continue
        break
        
    if not flag:
        print("cannot use the Chinese remainder theorem directly.")
        return 0

    Mj = []
    m = 1
    for i in range(number):
        m *= mj[i]
    for i in range(number):
        temp = m // mj[i]
        Mj.append(temp)

    Mjr = []
    for i in range(number):
        Mjr.append(MjrCal(Mj[i], mj[i]))

    x = 0
    for i in range(number):
        x += Mj[i] * Mjr[i] * a[i]
    x = x % m
    print("x = {}".format(x))


for i in range(1, 21):
    print(i, end=" : ")
    solCal(i)