本文最后更新于 261 天前，其中的信息可能已经有所发展或是发生改变。
RSA 1
例题
from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)
p = getPrime(128)
q = getPrime(128)
n = p * q
e = 65537
c = pow(m,e,n)
print(n,c)
# 62193160459999883112594854240161159254035770172137079047232757011759606702281
# 17331436837911040930486942133359735652484926528331507431552667656734821231501exp
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
e = 65537
p = 265147241000574873803071047177766359643 # yafu 分解
q = 234560843346150602519484260867514743467
c = 17331436837911040930486942133359735652484926528331507431552667656734821231501
_n = (p-1)*(q-1)
d = invert(e, _n)
m = pow(c, d, n)
print(long_to_bytes(m))RSA 2
例题
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852exp
import libnum
def egcd(a, b):
if (b == 0):
return 1, 0, a
else:
x, y, q = egcd(b, a % b) # q = GCD(a, b) = GCD(b, a%b)
x, y = y, (x - (a // b) * y)
return x, y, q
def mod_inv(a, b):
return egcd(a, b)[0] % b # 求a模b得逆
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
invq=mod_inv(p,q)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=((mp-mq)*invq % p)*q+mq
print(libnum.n2s(m))RSA 低指数攻击
例题
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n1 = p*q
e1 = 0x3
c1 = pow(m,e1,n1)
print(f'n1 = {n1}')
print(f'e1 = {e1}')
print(f'c1 = {c1}')
'''
n1 = 19920284552214772740140135352548541831031690920425912140961436065508824546041514076016684238261995522677433833330399269923572993489681770913908642529489382472548548664350078176417366141695108301338793624641102311886122714705781923892243561473766978666116035403145672686443197319003393949350402512739343998236331447680561106899174404316265329944969786438022711742891334905159259854026408058542492105569778656883811323759583727586331462200020945101286801110840081277963013591342157754264111051785385892113635682519079401538045775697382691195557344630571694510115674941400112478156619785019370731073096018975390492287333
e1 = 3
c1 = 1752041777918702842605810950957832076618830231626916748933875881505173164404519153781007066742915517004902508987841695668088780745675304779496841107726530280651344357647334690721873124324358539328142005709830859468027528835981960873390785515876157664035579935532043154959183555353553164481674735512873428044452976229459806219115571797514157279125
'''exp
import gmpy2
from Crypto.Util.number import *
def de(c, e, n):
k = 0
while True:
mm = c + n*k
result, flag = gmpy2.iroot(mm, e)
if True == flag:
return result
k += 1
e= 3
n= 19920284552214772740140135352548541831031690920425912140961436065508824546041514076016684238261995522677433833330399269923572993489681770913908642529489382472548548664350078176417366141695108301338793624641102311886122714705781923892243561473766978666116035403145672686443197319003393949350402512739343998236331447680561106899174404316265329944969786438022711742891334905159259854026408058542492105569778656883811323759583727586331462200020945101286801110840081277963013591342157754264111051785385892113635682519079401538045775697382691195557344630571694510115674941400112478156619785019370731073096018975390492287333
c= 1752041777918702842605810950957832076618830231626916748933875881505173164404519153781007066742915517004902508987841695668088780745675304779496841107726530280651344357647334690721873124324358539328142005709830859468027528835981960873390785515876157664035579935532043154959183555353553164481674735512873428044452976229459806219115571797514157279125
m=de(c,e,n)
print(long_to_bytes(m))RSA 欧拉函数
例题
from Crypto.Util.number import *
from secret import flag
pad = lambda x:x + bytes([16 - len(x)%16] * (16 - len(x)%16))
m = bytes_to_long(pad(flag))
p = getPrime(100)
q = getPrime(100)
n = p*p*q*q
e = 0x10001
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
print(f'e = {e}')
'''
n = 564070152909085514893862673848191100242629745476416876533996976389897932324860687952230733393080567203972999049426141761
c = 269509453821913281608300827585653465889617103481995203776655691658799441157871331220899710463748827149644657719450056013
e = 65537
'''exp
from Crypto.Util.number import *
from gmpy2 import invert
n = 564070152909085514893862673848191100242629745476416876533996976389897932324860687952230733393080567203972999049426141761
c = 269509453821913281608300827585653465889617103481995203776655691658799441157871331220899710463748827149644657719450056013
e = 65537
p = 1058314117179226194777612760717
q = 709662686105519282917793669093
_n = (p-1)*(q-1)*p*q
d = invert(e, _n)
m = pow(c, d, n)
print(long_to_bytes(m))RSA 扩展中国剩余定理
例题
from Crypto.Util.number import *
from secret import flag
p = getPrime(128)
q = getPrime(128)
n = p*p*q*q
a = getPrime(500)
m = bytes_to_long(flag)
c = pow(m,a,n)
print('p=',p)
print('q=',q)
print('c=',c)
print('ap=',a%(p*p*q))
print('aq=',a%(p*q*q))
'''
p= 188980719722312939599670741525749657199
q= 285542837410681929815185657243211948089
c= 1288716005120610238447107994487516282456949535157488967851890643249636143960514002885912602457300860833910005286646288391158486869716320731486731441463943
ap= 2804705527665993106616916539865422192745582325982115542328821379552303967198212155976104551702352092937673859677117
aq= 4474202009939446421702154845731790486027787037904256660458907755838647247389331585632003974919913796690158918283199
'''exp
from gmpy2 import invert
from Crypto.Util.number import *
"""扩展欧几里得"""
def exgcd(a, b):
if 0 == b:
return 1, 0, a
x, y, q = exgcd(b, a % b)
x, y = y, (x - a // b * y)
return x, y, q
"""扩展中国剩余定理"""
def CRT():
if n == 1:
if m[0] > a[0]:
return a[0]
else:
return -1
for i in range(n):
if m[i] <= a[i]:
return -1
x, y, d = exgcd(m[0], m[i])
if (a[i] - a[0]) % d != 0:
return -1
t = m[i] // d
x = (a[i] - a[0]) // d * x % t
a[0] = x * m[0] + a[0]
m[0] = m[0] * m[i] // d
a[0] = (a[0] % m[0] + m[0]) % m[0]
return a[0]
p= 188980719722312939599670741525749657199
q= 285542837410681929815185657243211948089
c= 1288716005120610238447107994487516282456949535157488967851890643249636143960514002885912602457300860833910005286646288391158486869716320731486731441463943
ap= 2804705527665993106616916539865422192745582325982115542328821379552303967198212155976104551702352092937673859677117
aq= 4474202009939446421702154845731790486027787037904256660458907755838647247389331585632003974919913796690158918283199
n = 2 # 同余方程个数
a = [ap, aq] # 余数
m = [p*p*q, p*q*q] # 模数
e = CRT()
_n = (p-1)*(q-1)*p*q
d = invert(e, _n)
m = pow(c, d, n)
print(long_to_bytes(m))RSA 利用 z3 解方程
例题
from Crypto.Util.number import getPrime, bytes_to_long
from flag import flag
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 0x10001
c = pow(m, e, n)
hint = p**5 - q**4
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"h = {hint}")
print(f"f = {flag}")
"""
n = 76236418318712173274495941060488893810931309177217802334230599201457092723011685048556311576262486371987147895332408646920500226769161418792142565209634495797142268681403865426056588605013602625268553194169434049817172340173907696496945054049859221379092764811535206778031226535614731731322630330166833765943
e = 65537
c = 7207616060389865156270906240837846478541820008527247539698331406253371238674590766101711421196342768182325013873320402422918804780590951789425587131632422554819735000106070325708057225062376701298825910565526713270553888227235612227223162695870584803109353377288421750982913226189395526612487664144379690552
h = 130285072635228037239175162118613869214302695058325046962039091162567931492116336918638092534964417960274466351834311039222269165021532950982276262717322395682559639859781516047319178212473103057947426886870612637975024605166325017663998263834789814181250953051730859433354534450232382414565421858172075431133498326501045697132640582932453817599366612200146802110424409285814189125929844293789544163802323048780585398714263586547670912817768592459281775837372982750626103047573532664320692775783627129463700810934670066747044799514243631607384814191188276380589420289084574680852618867732847029105400406874790675559126905078326495799755425006555539699119063191489852930421412630857588890593040420277938268954008973405431053073576987401154763326417551463323055736754390446
"""exp
from Crypto.Util.number import long_to_bytes
from z3 import *
from gmpy2 import invert
n = 76236418318712173274495941060488893810931309177217802334230599201457092723011685048556311576262486371987147895332408646920500226769161418792142565209634495797142268681403865426056588605013602625268553194169434049817172340173907696496945054049859221379092764811535206778031226535614731731322630330166833765943
e = 65537
c = 7207616060389865156270906240837846478541820008527247539698331406253371238674590766101711421196342768182325013873320402422918804780590951789425587131632422554819735000106070325708057225062376701298825910565526713270553888227235612227223162695870584803109353377288421750982913226189395526612487664144379690552
h = 130285072635228037239175162118613869214302695058325046962039091162567931492116336918638092534964417960274466351834311039222269165021532950982276262717322395682559639859781516047319178212473103057947426886870612637975024605166325017663998263834789814181250953051730859433354534450232382414565421858172075431133498326501045697132640582932453817599366612200146802110424409285814189125929844293789544163802323048780585398714263586547670912817768592459281775837372982750626103047573532664320692775783627129463700810934670066747044799514243631607384814191188276380589420289084574680852618867732847029105400406874790675559126905078326495799755425006555539699119063191489852930421412630857588890593040420277938268954008973405431053073576987401154763326417551463323055736754390446
# p, q = Int('x'), Int('y')
# solve(p ** 5 - q ** 4 == h, p * q == n)
p = 10543357481374908938696626650832667304979816176891429562773232136754485382413647547320866232418359800743787286242710171986152592431595912519025867918658127
q = 7230753434414569972828808651891325142186523078619542872286840414394373161212272545789342965212718184298307353595004152854764254216044770456139231711296409
_n = (p-1)*(q-1)
d = invert(e, _n)
m = pow(c, d, n)
print(long_to_bytes(m))RSA many factors 欧拉函数
例题
from Crypto.Util.number import *
from flag import flag
n = 1
for i in range(60):
f = getPrime(10)
n *= f
e = 65537
c = pow(bytes_to_long(flag.encode()), e, n)
# print(f"flag = {flag}")
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
"""
e = 65537
n = 36618139579386063246087882054063631367923586826293230665209915187491823328978276724908066032487515386697740611819366867179565337532194305783987450587518624526250530134446397
c = 3053043969587277731075013823380664207370991627277672374256662715889363487017560381573682876563907215099359894935326265406537547932246927604121814198201993671878573628633125
"""exp
from Crypto.Util.number import *
from gmpy2 import invert
e = 65537
n = 36618139579386063246087882054063631367923586826293230665209915187491823328978276724908066032487515386697740611819366867179565337532194305783987450587518624526250530134446397
c = 3053043969587277731075013823380664207370991627277672374256662715889363487017560381573682876563907215099359894935326265406537547932246927604121814198201993671878573628633125
factors = [521, 521, 521, 541, 547, 557, 557, 577, 587, 593, 601, 607, 631, 631, 631, 631, 641, 643, 683, 701, 701, 719, 727, 727, 727, 733, 739, 739, 743, 757, 761, 769, 773, 787, 787, 809, 821, 821, 821, 863, 877, 877, 881, 907, 907, 907, 907, 907, 919, 919, 929, 937, 953, 953, 967, 967, 991, 997, 997, 1019] # yafu 分解因子
_n = 1
for i in list(set(factors)):
_n *= (i - 1)
factors.remove(i)
for i in factors:
_n *= i
d = invert(e, _n)
m = pow(c, d, n)
print(long_to_bytes(m))RSA next prime
例题
from Crypto.Util.number import *
from gmpy2 import next_prime
from flag import flag
p = getPrime(1024)
q = next_prime(p)
n = p*q
e = 0x10001
c = pow(bytes_to_long(flag), e, n)
print(f"n = {n}")
print(f"c = {c}")
"""
n = 19421904767367129549329507820147867763064747101931314714173717122035977491291441314433180813343755107381230481007143328156292096871675328839756035726106037229325380698967544660649710464634698425387682458721466040894830503881966355435442651493212040443436714597490121865537266815247879839020846287255634123530517095030752832857842819836940083915495464712363169428825344678729929317207583197980607919720642725221740680718976635305544368542563503440076036727388062097647374046378854873864505267644315352602271587283702733779081805129429479541906613334092422428543951370065910195162721686773383508480268145903016615151713
c = 16430654037742749931837577925393394466626615745270895225352757745284038922799868617243616416116392338428121605256850230862894296244375242336599929497221079420665154174930054597666915358687410522457846003186806053368237783147731665147575913322026626738697036282908055611350347494310666532700194563684837580022875526378181343082801716942536163583090541294011987732281942148455345223347021675781368596340860151253774597168954881987520338304516390785094435356412111780768446904948045448510663589654475221029009283144829902553888829840193614048967712676048740814622290029846433107762872806981599110271586325156855299974310
"""exp
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert
def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
def fermat(n):
a = isqrt(n)
b2 = a * a - n
b = isqrt(n)
count = 0
while b * b != b2:
a = a + 1
b2 = a * a - n
b = isqrt(b2)
count += 1
p = a + b
q = a - b
assert n == p * q
return p, q
n = 19421904767367129549329507820147867763064747101931314714173717122035977491291441314433180813343755107381230481007143328156292096871675328839756035726106037229325380698967544660649710464634698425387682458721466040894830503881966355435442651493212040443436714597490121865537266815247879839020846287255634123530517095030752832857842819836940083915495464712363169428825344678729929317207583197980607919720642725221740680718976635305544368542563503440076036727388062097647374046378854873864505267644315352602271587283702733779081805129429479541906613334092422428543951370065910195162721686773383508480268145903016615151713
c = 16430654037742749931837577925393394466626615745270895225352757745284038922799868617243616416116392338428121605256850230862894296244375242336599929497221079420665154174930054597666915358687410522457846003186806053368237783147731665147575913322026626738697036282908055611350347494310666532700194563684837580022875526378181343082801716942536163583090541294011987732281942148455345223347021675781368596340860151253774597168954881987520338304516390785094435356412111780768446904948045448510663589654475221029009283144829902553888829840193614048967712676048740814622290029846433107762872806981599110271586325156855299974310
e = 0x10001
p, q = fermat(n)
_n = (p-1)*(q-1)
d = invert(e, _n)
m = pow(c, d, n)
print(long_to_bytes(m))RSA 共模攻击
例题
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2 = 9647291exp
import gmpy2
import libnum
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2 = 9647291
# s1=gmpy2.invert(e1,e2)
# s2=gmpy2.invert(e2,e1)
r, s1, s2 = gmpy2.gcdext(e1, e2)
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
print(hex(m))
print(libnum.n2s(int(m)))dp泄露
例题
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751exp
import gmpy2 as gp
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
for i in range(1, e): # 在范围(1,e)之间进行遍历
if (dp * e - 1) % i == 0:
if n % (((dp * e - 1) // i) + 1) == 0: # 存在p，使得n能被p整除
p = ((dp * e - 1) // i) + 1
q = n // (((dp * e - 1) // i) + 1)
phi = (q - 1) * (p - 1) # 欧拉定理
d = gp.invert(e, phi) # 求模逆
m = pow(c, d, n) # 快速求幂取模运算
print(bytes.fromhex(hex(m)[2:])) # 16进制转文本Rabin
例题
from Crypto.Util.number import *
def gen_key(kbits):
while True:
p = getPrime(kbits)
q = getPrime(kbits)
if p % 4 == 3 and q % 4== 3:
break
return p, q
p ,q = gen_key(256)
flag = open("flag", 'rb').read()
pt = bytes_to_long(flag)
c = pow(pt, 2, p*q)
print(f"p={p}\nq={q}")
print(f"c={hex(c)[2:]}")
"""
p=65428327184555679690730137432886407240184329534772421373193521144693375074983
q=98570810268705084987524975482323456006480531917292601799256241458681800554123
c=4e072f435cbffbd3520a283b3944ac988b98fb19e723d1bd02ad7e58d9f01b26d622edea5ee538b2f603d5bf785b0427de27ad5c76c656dbd9435d3a4a7cf556
"""exp
from Crypto.Util.number import *
import gmpy2
p = 65428327184555679690730137432886407240184329534772421373193521144693375074983
q = 98570810268705084987524975482323456006480531917292601799256241458681800554123
c = 0x4e072f435cbffbd3520a283b3944ac988b98fb19e723d1bd02ad7e58d9f01b26d622edea5ee538b2f603d5bf785b0427de27ad5c76c656dbd9435d3a4a7cf556
e = 2
n = p * q
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
yp = gmpy2.invert(p, q)
yq = gmpy2.invert(q, p)
r = (yp * p * mq + yq * q * mp) % n
rr = n - r
s = (yp * p * mq - yq * q * mp) % n
ss = n - s
for i in [r, rr, s, rr]:
print(long_to_bytes(i))低指数广播攻击
例题
from Crypto.Util.number import *
from secret import flag
e = 17
m = bytes_to_long(flag)
p1 = getPrime(1024)
q1 = getPrime(1024)
n1 = p1 * q1
p2 = getPrime(1024)
q2 = getPrime(1024)
n2 = p2 * q2
p3 = getPrime(1024)
q3 = getPrime(1024)
n3 = p3 * q3
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)
print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'n3 = {n3}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
'''
n1 = 13653211321911743284480909525276872078640800319621776477330467667298869996185121594087659533908559485366031321482941649833599620676150979492615096544753920303402429289553047461012405904119674512178450680663049321742438434064155322869447738748863615140240157577333437289660059729778480733302800586692231519806920661104597582412369155794198534143625241519497158863582486843704256127210420826545465147704974055735454963293576714142928266547844017951003140209264228384724407438697170151590745765926671486699036005349835210789316259504105933738582020417244945353384708887656570875124178933267935130848955938775744758541707
n2 = 25600858391665956508392292297999994627768746577413039861089667474129387404956196685280854195513497550832244914673331145507381077896093227119510606240142044315436619488183820647772909899999064392225124236979496184122480098866707513362947357725527142283749304879758903779522269036233838831284116137966191040812205570432387699366939598202960067758319351768733306637609012368552366030812795693376956416920871592225702949403785505476966638502602161510619622310259435833098107929844609256343203483027710774143561921864588283753117428548717379793355076767446281591229744734057382322903155034671260187231942841821716792531403
n3 = 24141712953184224584682542895484641041414330469843336508170124452265963177451990879263887386428323626848290333745466237839909725737610209748162954054625431684501681138353393798939695051704172535689041272879516044085113887876911483752877142309100433506461644618643793311179275305270193866560148229575278322305189943793686809137376373498374714350212683823698900511183192901271850591685674903541060235915779984234798267660746221856056878846326486945381849316312500877094258282855324966309234336344566644546581963348970234855143498069269930887148219808894900878372403311461333204468974970085715904527790183955322099838177
c1 = 12135122155779995880342959345483283131738712887680553285778212743598014742465083614779313128239014216027450730685733443148640298441346974122358116068692712598413402472654916752810242776352584497158664624502758185908207559358307188961049786286239735848939908735370385429911238029465961452407583846409998646795126147145436060695077013737116908593924340568208358448522273082764783916866172577059183386768510520789888375565894297286053169313998041256507993508856547374264823928445295155654728911050768141834581359633085627779020515263780733347165152808881322305858650163974749769866446639003776062787965624325862898409541
c2 = 8449280958486680404093958757880880524882773154529690529289796056974548338344696889360040509522827575431226512823023492719335636623430600494826565544462094031890676366252273586104427026900502179627965055034160581838881047405599282895506136110153312620323562564321321583851153376813432150606662439508645248366677613490840020798743969766983161801425083686613661298707259867843535734412442298753779434028506617205754732400048351976725392491724773597309236194094845520140888301508084127369216742751644974072582102825210677417859360583662424787371245513699346603005290701909976079837028709864188847618137611199684141570944
c3 = 22417046630173396294162232887001557548671376610674319237840976539784237834624521447936115760217033709098086972981019126545102620589235335463006534231807545114056891997390251334910379893988142041395132663313641744523968205802034310921480467684458218583845290418343688193196963801619456389755619792424509489744100062209894330178618592726296459760903363713002746272708577642993288966202722935451330555629691480886700942560592636456797194377988638659691099769719002975363031882314202763583667760471281096772144979691526227115462265606176555601445602313642786054504580445291376221216946557281880096336939884211975935061760
'''
exp
import libnum
from gmpy2 import invert, gcd, iroot
def op(x):
res = 1
for i in x:
res *= i
return res
def CRT(m, a):
assert (len(m) == len(a))
M = op(m)
sum = 0
for m, a in zip(m, a):
Mi = M // m
ti = invert(Mi, m)
sum += a * ti * Mi
return sum % M
def GCRT(m, a):
assert (len(m) == len(a))
curm, cura = m[0], a[0]
for m, a in zip(m[1:], a[1:]):
d = gcd(curm, m)
c = a - cura
assert (c % d == 0)
K = c // d * invert(curm // d, m // d)
cura += curm * K
curm = curm * m // d
return cura % curm
e = 17
n = [n1, n2, n3]
c = [c1, c2, c3]
m = CRT(n, c)
m1 = iroot(m, e) # 开e次方
print(m1)
print(libnum.n2s(int(m1[0])))
