# 由suctf一道题学到的中国余子式定理

minwei.wang@dbappsecurity.com.cn

“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”，这首诗的意思是有一个数，除以三余数为二，除以五余数问三，除以七余数为二，求这个数。

①令除数n1=3，n2=5，n3=7两两互质，然后将除数相乘得到一个n，n=n1n2n3=105;

②令余数x1=2，x2=3，x3=2，令乘积除以每个除数，得到一组数，M1=n/n1=105/3=35，M2=n/n2=105/5=21，M3=n/n3=105/7=15;

③利用辗转相除法或直接计算乘法反元素得到一组数：

s1=(mod n1) = ≡ 2 (mod 3)

s2=(mod n2) = ≡ 1 (mod 5)

s3=(mod n3) = ≡ 1 (mod 7)

④最后将每对M、x、s求乘积并将每对数据相加求和，将结果对n取余数，就可以得到最终的结果。

X = (x1M1s1 + x2M2s2 + x3M3s3) (mod n)

= (2×35×2 + 3×21×1 + 2×15×1) (mod 105)

= 23

x=

import gmpy2

n = [3,5,7]

x = [2,3,2]

N = 1

for i in n:

N *= i

M = []

for i in n:

M.append(N/i)

s = []

for i in range(len(n)):

s.append(gmpy2.invert(M[i],n[i]))

#print s

sum = 0

for i in range(len(n)):

sum += x[i] * M[i] * s[i]

X = sum % N

print X

Game.py内容：

import flag

flag = flag.flag

sands = int(flag[5:-1].encode("hex"), 16)

holes = [257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373]

with open("sand.txt", "w") as f:

for i in range(len(holes)):

sand = sands % holes[i]

f.write(str(sand)+"\n")

#coding:utf-8

import gmpy2

with open('sand.txt','r') as f:

sands = []

for i in sand_src:

sands.append(int(i.replace('\n','')))

holes = [257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373]

n = 1

for i in holes:

n *= i

M = []

for i in holes:

M.append(n/i)

s = []

for i in range(len(holes)):

s.append(gmpy2.invert(M[i],holes[i]))

#print s

x = 0

for i in range(len(sands)):

x += sands[i] * M[i] * s[i]

res = x % n

#print res

encode_hex = hex(res).replace('0x','').replace('L','')

decode_hex = encode_hex.decode('hex')

flag = "flag{" + decode_hex + "}"

print flag

-END-

177 篇文章73 人订阅

0 条评论

## 相关文章

33312

3316

4947

1211

1733

3065

2816

### 1163 访问艺术馆

时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解  查看运行结果 题目描述 Description     皮尔...

2757

2914

35510