# 中国剩余定理

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 = []
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)``````