この記事では、KSNCTF の問題17について解説をしている。

目次

1. はじめに
2. 問題概要
- 2.1 問題文の確認
- 2.2 ニュートン法を使った解法
3. さいごに
4. 参考資料

1. はじめに

本記事では、ksnctf の問題17 Math II の解説を行う。

2. 問題概要

2.1. 問題文の確認

問題文は以下の通りである。

問題

Let
x = 2748040023408750324411119450523386950660946398855386842074606380418316981389557916980086140301887947706700698930830779678048474531538039134089675000612962004189001422715316147779554460684462041893073445562829316520071658956471592707597247194589999870235577599858641217209525243986680999448565468816434633441308131788183291153809253610695081752296732033298647222814340913466738465892791206393936089466068684809286651197884210187525269355913763182559833600649423167126622527203197940618965341674710993871930168655984019611567024681974446413864111651893113475795042753452042221938667445789706741508160949598322950403760355305740757495122850819958219745478009476321531997688864567881328571570240278649150057863614800304034452842380274161491817926949213762740941829027657311016236224840157689532838274458699038989430527152474540367086746579688987076042252804910459873636444778218434530247647760637770881658596016745610672707638583665201858035977485748775481448417394363801163664632527695106599930657132405666766730530997168969743603771751166591137309462845077320233889570871715682231576283485837079838925927845291565664213349164253238166525895494203520538861102027123057706413048503799598270037162337386882901940037500301040636118696723417952777083334146545991127148023661461455142653367976629308434919237639329808504561590505864983890552051987234096577849288536293631380950881787840319976968198704697701966146561843819563765280293823120028941691560894722032503932540560461794190408016359786029679686957711035845785762377768203676919060935155382104877926736292611130243057909501332528103700463961697932230444978571571548190911155741113324573679444638703192583211952316173122745153529542339170631749363019742630339456502772150867703497326010832217054307087826776870481852284816747574983354077170761286175754243223519482572371717625453405597596790583499145036350302955327521461648262537855645876387858201576107385450844609238327605056916243564458120595540013872075267316304999752934829122583429168665162743589578036716137649553856654996867605565582594039606555708509284616434305172100068285925706963351193710675088846623856567419346569873886366829228933416064828304824833588800700991940600359503453201939139663042787644390810036292415117714919711827630953170559057272633043896443339064006637234499569232762828723613158050896065355005775876910820958296537497557737916521798848004761708690607167573807307291510879396794861418856342383200817566360552405183866698509354047737422523253071467100174078467454351746681775690022510266842064132386305358891086764558955802257688899610117102582837343655907837234028334304769930810792079059216436489942124896722072971246781926084943216581585837400274934104255861076781834022322597318553478829221018993823759479304536464719195824731739557957722610850860725276329731096193041588880149698625007746958307472328762247329346952956782896672291984502790479223886842985800649168009891087704339671376795754679245964575179873102014722210341771266309855717402003098724600141420936602986387680283404929020457247001371544838792904086327642729822000980710278752669990211765608002907900832262843253793831541691706704836397397798869236939393204666502455311086553874765248631328418556164635889080357612074921368044611251307530838475840480894307375072202500636365832958938363048173011687247738236161480446422712858040552310006617829659443118541556912488329721272939472554467384944920030182974546889304443711910957344160175437149714520561879951921970795705645045936350875827028675689840953101114431720413756855193291198455863087675930604549263160397353363504597829924339064422377323361781720524799661393081986371074530022532621955945720583925291264598924971169093688390536693144593482790588893095052569365154072722966434676949346037949263628957665599420417719951187489606010866702371368012263032537375401145460592536898818245350468847674995676417425737655723761467908866712060720593684978725896677308273.

Find the value of $y$ such that $y ^ {101} = x$.

The flag is FLAG_y (in decimal notation).

巨大な $x$ が与えられて、これの 101 乗根を求める必要がある。単純に計算をすると、多倍長整数を扱うことができる Python でも、計算をすることができない。以下に組み込み関数 pow を利用して、単純に計算した時のソースコードとその実行結果を示す。

2.1.1 pow 演算のソースコード

print(pow(x, -101)) #

2.1.2 実行結果

Traceback (most recent call last):
  File "/mnt/c/Users/sfuji/dev_workspace/main.py", line 40, in <module>
    print(pow(x, -101))
          ^^^^^^^^^^^^
OverflowError: int too large to convert to float

実行結果より、OverflowError が発生し、解を求めることができない。

そのため、高速に解を求めることができるニュートン法を使って求めていく。

2.2. ニュートン法を使った解法

ニュートン法の手順は、以前に解説したバビロニアの平方根の記事で解説している。

では、実際にニュートン法を使って計算していく。初めに求める式 $y ^ {101} = x$ から、ニュートン法を適用するために、関数形式に書き換えて、

\begin{align}
f(y)  &= y^{101} - x \\
f'(y) &= 101 y  ^ {100}
\end{align}

の2式を得る。これをニュートン法の式に当てはめて計算をしていくと、

\begin{align}
y_{n+1} &= y_n - \dfrac{f(y_n)}{f'(y_n)} \\
        &= y_n - \dfrac{y_n ^ {101} - x}{101 y_n ^ {100}} \\
        &= \dfrac{101 y_n ^ {101} - (y_n ^ {101} - x)}{101 y_n ^ {100}} \\
        &= \dfrac{100 y_n ^ {101} + x}{101 y_n ^ {100}} \\
        &= (100 y_n + \dfrac{x}{y_n ^ {100}}) \times \dfrac{1}{101}
\end{align}

となり、$y_{n+1}$ の式を得ることができる。この式を使って、ニュートン法を適用していく。

2.2.1. ニュートン法の初期値の定め方

次に初期値を定める。初期値 $y_0$ をどのように設定するのかが、ニュートン法の収束速度に大きく影響する。ここでは、$x$ のビット長から、おおよその $y$ のサイズを見積もるという方法を取る。

$y ^ {101} = x$ より、両辺にビット長の対数（底2）を取ると、

\begin{align}
\log_{2}{y ^ {101}}     &= \log_{2}{x} \\
101 \times \log_{2}{y} &= \log_{2}{x} \\
\log_{2}{y} &= \dfrac{\log_{2}{x}}{101} \\
y &= 2 ^ {\tfrac{\log_{2}{x}}{101}}
\end{align}

となる。これはつまり、$y$ のおおよその値は、2 の $\dfrac{\log_{2}{x}}{101}$ 乗となる。$\log_{2}{x}$ は $x$ のビット長であるので、

y0 = 1 << (x.bit_length() // 101)

と設定すればよい。

2.2.2. ニュートン法ソースコード

ソースコードは以下の通り。

x = 2748040023408750324411119450523386950660946398855386842074606380418316981389557916980086140301887947706700698930830779678048474531538039134089675000612962004189001422715316147779554460684462041893073445562829316520071658956471592707597247194589999870235577599858641217209525243986680999448565468816434633441308131788183291153809253610695081752296732033298647222814340913466738465892791206393936089466068684809286651197884210187525269355913763182559833600649423167126622527203197940618965341674710993871930168655984019611567024681974446413864111651893113475795042753452042221938667445789706741508160949598322950403760355305740757495122850819958219745478009476321531997688864567881328571570240278649150057863614800304034452842380274161491817926949213762740941829027657311016236224840157689532838274458699038989430527152474540367086746579688987076042252804910459873636444778218434530247647760637770881658596016745610672707638583665201858035977485748775481448417394363801163664632527695106599930657132405666766730530997168969743603771751166591137309462845077320233889570871715682231576283485837079838925927845291565664213349164253238166525895494203520538861102027123057706413048503799598270037162337386882901940037500301040636118696723417952777083334146545991127148023661461455142653367976629308434919237639329808504561590505864983890552051987234096577849288536293631380950881787840319976968198704697701966146561843819563765280293823120028941691560894722032503932540560461794190408016359786029679686957711035845785762377768203676919060935155382104877926736292611130243057909501332528103700463961697932230444978571571548190911155741113324573679444638703192583211952316173122745153529542339170631749363019742630339456502772150867703497326010832217054307087826776870481852284816747574983354077170761286175754243223519482572371717625453405597596790583499145036350302955327521461648262537855645876387858201576107385450844609238327605056916243564458120595540013872075267316304999752934829122583429168665162743589578036716137649553856654996867605565582594039606555708509284616434305172100068285925706963351193710675088846623856567419346569873886366829228933416064828304824833588800700991940600359503453201939139663042787644390810036292415117714919711827630953170559057272633043896443339064006637234499569232762828723613158050896065355005775876910820958296537497557737916521798848004761708690607167573807307291510879396794861418856342383200817566360552405183866698509354047737422523253071467100174078467454351746681775690022510266842064132386305358891086764558955802257688899610117102582837343655907837234028334304769930810792079059216436489942124896722072971246781926084943216581585837400274934104255861076781834022322597318553478829221018993823759479304536464719195824731739557957722610850860725276329731096193041588880149698625007746958307472328762247329346952956782896672291984502790479223886842985800649168009891087704339671376795754679245964575179873102014722210341771266309855717402003098724600141420936602986387680283404929020457247001371544838792904086327642729822000980710278752669990211765608002907900832262843253793831541691706704836397397798869236939393204666502455311086553874765248631328418556164635889080357612074921368044611251307530838475840480894307375072202500636365832958938363048173011687247738236161480446422712858040552310006617829659443118541556912488329721272939472554467384944920030182974546889304443711910957344160175437149714520561879951921970795705645045936350875827028675689840953101114431720413756855193291198455863087675930604549263160397353363504597829924339064422377323361781720524799661393081986371074530022532621955945720583925291264598924971169093688390536693144593482790588893095052569365154072722966434676949346037949263628957665599420417719951187489606010866702371368012263032537375401145460592536898818245350468847674995676417425737655723761467908866712060720593684978725896677308273

init = 1 << (x.bit_length() // 101)
yn = init

while True:
	power_100 = pow(yn, 100)

	next_step = (100 * yn + x // power_100) // 101

	if next_step == yn:
		break

	yn = next_step

if pow(yn, 101) == x:
	print(f"FLAG_{yn}")
else:
	print("NG")

2.2.3. 実行結果

実行した結果は次の通りである。

FLAG_545783032743911043438387247245888260273

ニュートン法を使用して、求めるFLAGの値を得ることができた。

3. さいごに

今回はKSNCTFの問題に取り組んだ。巨大な数の指数根は一見すると、求めることが出来ないように見えるが、ニュートン法を使うことで、現実的な時間の範囲で答えを得ることができる。

4. 参考資料

[1]. KSNCTF Math II

[2]. 平方根を高速に求めるバビロニアの平方根

[3]. Python の整数型はどのように実装されているのか