中国剩余定理_同余式的解遍历

中国剩余定理：
设m1,…,mk是k个两两互素的正整数，则对任意的整数b1,…,bk，同余式组：
x ≡ b1 (mod m1)
……
……
……
x = bk (mod mk)
一定有解，且解是唯一的。
(1)若令m = m1*…*mk，m = mi * Mi, i = 1,…k
则同余式组的解可以表示为
x ≡ b1 * M1’ * M1 + … + bk * Mk’ * Mk （mod m）
其中Mi’为Mi模mi的逆元，即Mi’ * Mi ≡ 1 (mod mi)，i = 1,…,k
(2)若令Ni = m(1) * … * m(i-1), Mi = m(1) * … * m(i)
同余式的解满足递归公式
x(i) ≡ (x(i-1) + ((b(i) - x(i-1)) * N’(i-1) mod m(i)) * N(i-1) ) mod M(i)，(i>2)
其中N’(i)为模m(i+1)的逆元，即N’(i) * N(i) ≡ 1 (mod m(i+1))

import libnum
import gmpy2
#法2
#递归
data = [[1,5],[5,6],[4,7],[10,11]] #[b,m]
m = 1
for i in data:
    m *= i[1]

def ZGSY(n,m):
    mi = data[n]
    if n == 0:
        return mi[0]
    pre_x = ZGSY(n-1,m//mi[1])
    N = m//mi[1]
    Nn = int(gmpy2.invert(N,mi[1]))
    x = (pre_x + ((mi[0]-pre_x)*Nn%mi[1])*N) % m
    return x

print(ZGSY(3,m))

#递推
'''
data = [[8,23],[4,29]]#[[1,5],[5,6],[4,7],[10,11]]
n = m = data[0][1]
x = data[0][0]
pd = 1
while pd<2:
    mi = data[pd]
    n = m
    m *=mi[1]
    nn = int(gmpy2.invert(n,mi[1]))
    x = (x+((mi[0] - x) * nn % mi[1])*n)% m     
    pd += 1
print(x)
'''

#法1
'''
data = [[8,23],[4,29]]
m = 1
for i in data:
    m *= i[1]
x = 0
for i in range(2):
    M = m//data[i][1]
    Mn = int(gmpy2.invert(M,data[i][1]))
    x = (x + data[i][0]*M*Mn)%m
print(x)
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

高端的代码:

#广播攻击
import gmpy2,libnum
from Crypto.Util.number import long_to_bytes,bytes_to_long


def broadcast_attack(data):
    def extended_gcd(a,b):
        x,y = 0,1
        lastx,lasty = 1,0
        while b:
            a,(q,b) = b,divmod(a,b)
            x,lastx = lastx-q*x,x
            y,lasty = lasty-q*y,y
        return (lastx,lasty,a)
    def chinese_remaindor_theorem(items):
        N = 1
        for a,n in items:
            N *= n
        result = 0
        for a,n in items:
            m = N//n
            r,s,d = extended_gcd(n,m)
            if d != 1:
                N = N//n
                continue
            result += a*s*m
        return result%N ,N
    x,n = chinese_remaindor_theorem(data)
    m = int(gmpy2.iroot(x,3)[0])
    return m

N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5) 
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5) 
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)
data = [(c1,N1),(c2,N2),(c3,N3)]
print(long_to_bytes(broadcast_attack(data)))


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44