Contents

中国剩余定理

Contents

记个模板题

题目给了以下条件:

$$\begin{cases} M^e \equiv C_1 mod\;N_1 \\[2ex] M^e \equiv C_2 mod\;N_2\quad \quad (e = 3) \\[2ex] M^e \equiv C_3 mod\;N_3 \end{cases} $$

1
2
3
4
5
6
7
8
9
c1 = 388825822870813587493154615238012547494666151428446904627095554917874019374474234421038941934804209410745453928513883448152675699305596595130706561989245940306390625802518940063853046813376063232724848204735684760377804361178651844505881089386
c2 = 4132099145786478580573701281040504422332184017792293421890701268012883566853254627860193724809808999005233349057847375798626123207766954266507411969802654226242300965967704040276250440511648395550180630597000941240639594
c3 = 43690392479478733802175619151519523453201200942800536494806512990350504964044289998495399805335942227586694852363272883331080188161308470522306485983861114557449204887644890409995598852299488628159224012730372865280540944897915435604154376354144428


n1 = 924506488821656685683910901697171383575761384058997452768161613244316449994435541406042874502024337501621283644549497446327156438552952982774526792356194523541927862677535193330297876054850415513120023262998063090052673978470859715791539316871
n2 = 88950937117255391223977435698486265468789676087383749025900580476857958577458361251855358598960638495873663408330100969812759959637583297211068274793121379054729169786199319454344007481804946263873110263761707375758247409
n3 = 46120424124283407631877739918717497745499448442081604908717069311339764302716539899549382470988469546914660420190473379187397425725302899111432304753418508501904277711772373006543099077921097373552317823052570252978144835744949941108416471431004677

套中国剩余定理公式就可以了

 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

import gmpy2
import binascii
from libnum import invmod

c1 = 388825822870813587493154615238012547494666151428446904627095554917874019374474234421038941934804209410745453928513883448152675699305596595130706561989245940306390625802518940063853046813376063232724848204735684760377804361178651844505881089386
c2 = 4132099145786478580573701281040504422332184017792293421890701268012883566853254627860193724809808999005233349057847375798626123207766954266507411969802654226242300965967704040276250440511648395550180630597000941240639594
c3 = 43690392479478733802175619151519523453201200942800536494806512990350504964044289998495399805335942227586694852363272883331080188161308470522306485983861114557449204887644890409995598852299488628159224012730372865280540944897915435604154376354144428


n1 = 924506488821656685683910901697171383575761384058997452768161613244316449994435541406042874502024337501621283644549497446327156438552952982774526792356194523541927862677535193330297876054850415513120023262998063090052673978470859715791539316871
n2 = 88950937117255391223977435698486265468789676087383749025900580476857958577458361251855358598960638495873663408330100969812759959637583297211068274793121379054729169786199319454344007481804946263873110263761707375758247409
n3 = 46120424124283407631877739918717497745499448442081604908717069311339764302716539899549382470988469546914660420190473379187397425725302899111432304753418508501904277711772373006543099077921097373552317823052570252978144835744949941108416471431004677

_M = n1*n2*n3
m1 = _M//n1
m2 = _M//n2
m3 = _M//n3

t1 = invmod(m1, n1)
t2 = invmod(m2, n2)
t3 = invmod(m3, n3)

_X = (c1*t1*m1 + c2*t2*m2 + c3*t3*m3) % _M
a = gmpy2.iroot(_X, 3)

print((gmpy2.iroot(_X, 3)))
s = hex(949557364767986162692541204888383714648410089749288993554212847615599100096583727459)


s = binascii.a2b_hex(s[2:-1])
print(s[::-1])


# cybrics{h3y_guY5_c0m3_t0_my_p4rtY!}

其实一般用得到的是中国剩余定理的扩展 =v=