ksnctf Q17 mathII

問題文

Math II - ksnctf

How important is modulo arithmetic in cryptography?

Let x = 2748040023408750324411119450523386950660946398855386842074606380418316981389557916980086140301887947706700698930830779678048474531538039134089675000612962004189001422715316147779554460684462041893073445562829316520071658956471592707597247194589999870235577599858641217209525243986680999448565468816434633441308131788183291153809253610695081752296732033298647222814340913466738465892791206393936089466068684809286651197884210187525269355913763182559833600649423167126622527203197940618965341674710993871930168655984019611567024681974446413864111651893113475795042753452042221938667445789706741508160949598322950403760355305740757495122850819958219745478009476321531997688864567881328571570240278649150057863614800304034452842380274161491817926949213762740941829027657311016236224840157689532838274458699038989430527152474540367086746579688987076042252804910459873636444778218434530247647760637770881658596016745610672707638583665201858035977485748775481448417394363801163664632527695106599930657132405666766730530997168969743603771751166591137309462845077320233889570871715682231576283485837079838925927845291565664213349164253238166525895494203520538861102027123057706413048503799598270037162337386882901940037500301040636118696723417952777083334146545991127148023661461455142653367976629308434919237639329808504561590505864983890552051987234096577849288536293631380950881787840319976968198704697701966146561843819563765280293823120028941691560894722032503932540560461794190408016359786029679686957711035845785762377768203676919060935155382104877926736292611130243057909501332528103700463961697932230444978571571548190911155741113324573679444638703192583211952316173122745153529542339170631749363019742630339456502772150867703497326010832217054307087826776870481852284816747574983354077170761286175754243223519482572371717625453405597596790583499145036350302955327521461648262537855645876387858201576107385450844609238327605056916243564458120595540013872075267316304999752934829122583429168665162743589578036716137649553856654996867605565582594039606555708509284616434305172100068285925706963351193710675088846623856567419346569873886366829228933416064828304824833588800700991940600359503453201939139663042787644390810036292415117714919711827630953170559057272633043896443339064006637234499569232762828723613158050896065355005775876910820958296537497557737916521798848004761708690607167573807307291510879396794861418856342383200817566360552405183866698509354047737422523253071467100174078467454351746681775690022510266842064132386305358891086764558955802257688899610117102582837343655907837234028334304769930810792079059216436489942124896722072971246781926084943216581585837400274934104255861076781834022322597318553478829221018993823759479304536464719195824731739557957722610850860725276329731096193041588880149698625007746958307472328762247329346952956782896672291984502790479223886842985800649168009891087704339671376795754679245964575179873102014722210341771266309855717402003098724600141420936602986387680283404929020457247001371544838792904086327642729822000980710278752669990211765608002907900832262843253793831541691706704836397397798869236939393204666502455311086553874765248631328418556164635889080357612074921368044611251307530838475840480894307375072202500636365832958938363048173011687247738236161480446422712858040552310006617829659443118541556912488329721272939472554467384944920030182974546889304443711910957344160175437149714520561879951921970795705645045936350875827028675689840953101114431720413756855193291198455863087675930604549263160397353363504597829924339064422377323361781720524799661393081986371074530022532621955945720583925291264598924971169093688390536693144593482790588893095052569365154072722966434676949346037949263628957665599420417719951187489606010866702371368012263032537375401145460592536898818245350468847674995676417425737655723761467908866712060720593684978725896677308273.

Find the value of y such that y¹⁰¹ = x.

The flag is FLAG_y (in decimal notation).

やってみる

「累乗根で出せる！」と思ったら、そんな単純な話ではなかった。
値がでかすぎるので、当然オーバーフローしてしまった。

yの値に101をべき乗して、xと同じ値を探すのが正攻法らしい。
y=1から一個一個やると果てしなく時間がかかるので、二分探索を使って求める。（らしい）

答え

x = 2748040023408750324411119450523386950660946398855386842074606380418316981389557916980086140301887947706700698930830779678048474531538039134089675000612962004189001422715316147779554460684462041893073445562829316520071658956471592707597247194589999870235577599858641217209525243986680999448565468816434633441308131788183291153809253610695081752296732033298647222814340913466738465892791206393936089466068684809286651197884210187525269355913763182559833600649423167126622527203197940618965341674710993871930168655984019611567024681974446413864111651893113475795042753452042221938667445789706741508160949598322950403760355305740757495122850819958219745478009476321531997688864567881328571570240278649150057863614800304034452842380274161491817926949213762740941829027657311016236224840157689532838274458699038989430527152474540367086746579688987076042252804910459873636444778218434530247647760637770881658596016745610672707638583665201858035977485748775481448417394363801163664632527695106599930657132405666766730530997168969743603771751166591137309462845077320233889570871715682231576283485837079838925927845291565664213349164253238166525895494203520538861102027123057706413048503799598270037162337386882901940037500301040636118696723417952777083334146545991127148023661461455142653367976629308434919237639329808504561590505864983890552051987234096577849288536293631380950881787840319976968198704697701966146561843819563765280293823120028941691560894722032503932540560461794190408016359786029679686957711035845785762377768203676919060935155382104877926736292611130243057909501332528103700463961697932230444978571571548190911155741113324573679444638703192583211952316173122745153529542339170631749363019742630339456502772150867703497326010832217054307087826776870481852284816747574983354077170761286175754243223519482572371717625453405597596790583499145036350302955327521461648262537855645876387858201576107385450844609238327605056916243564458120595540013872075267316304999752934829122583429168665162743589578036716137649553856654996867605565582594039606555708509284616434305172100068285925706963351193710675088846623856567419346569873886366829228933416064828304824833588800700991940600359503453201939139663042787644390810036292415117714919711827630953170559057272633043896443339064006637234499569232762828723613158050896065355005775876910820958296537497557737916521798848004761708690607167573807307291510879396794861418856342383200817566360552405183866698509354047737422523253071467100174078467454351746681775690022510266842064132386305358891086764558955802257688899610117102582837343655907837234028334304769930810792079059216436489942124896722072971246781926084943216581585837400274934104255861076781834022322597318553478829221018993823759479304536464719195824731739557957722610850860725276329731096193041588880149698625007746958307472328762247329346952956782896672291984502790479223886842985800649168009891087704339671376795754679245964575179873102014722210341771266309855717402003098724600141420936602986387680283404929020457247001371544838792904086327642729822000980710278752669990211765608002907900832262843253793831541691706704836397397798869236939393204666502455311086553874765248631328418556164635889080357612074921368044611251307530838475840480894307375072202500636365832958938363048173011687247738236161480446422712858040552310006617829659443118541556912488329721272939472554467384944920030182974546889304443711910957344160175437149714520561879951921970795705645045936350875827028675689840953101114431720413756855193291198455863087675930604549263160397353363504597829924339064422377323361781720524799661393081986371074530022532621955945720583925291264598924971169093688390536693144593482790588893095052569365154072722966434676949346037949263628957665599420417719951187489606010866702371368012263032537375401145460592536898818245350468847674995676417425737655723761467908866712060720593684978725896677308273


lo = 0
hi = pow(10,100)

while True:
    md = (lo + hi) // 2
    print(md)
    if pow(md, 101) > x:
        hi = md - 1
    elif pow(md, 101) < x:
        lo = md + 1
    else:
        print(md)
        break

timeモジュールでtime.sleep(0.25)でちょっと遅らせると、値が求められていく様子が見えて面白い。

参考文献

ksnctf #17 Math II - 俺より凄いやつしかいない。