TSGCTF 2021 | Lumberjack in Nature

tsgctf_2021 算数 テイラー展開 sage_magic

#TSGCTF_2021

from mpmath import mp, power, ln
import json

mp.dps = 1000000000

def decode(enc):
    return int(power(2, enc * ln(2)))

s, e = json.load(open('encoded.json'))
flag = decode(s << e)

print(flag.to_bytes((flag.bit_length() + 7) // 8, 'big')[:74])

算数

やってることは 2^{s*2^e \ln2}

e = 13371337

でめちゃくちゃでかくてどうしようもない

テイラー展開すると

\ln2 = \sum_{n=1}^\infin \frac{1}{2^nn}

したがって

s*2^e \ln2 = \sum \frac{s*2^e}{2^nn} = \sum \frac{s*2^{e-n}}{n}

……よくわかりません

別解

これは何？ sage magic

R = RealField(2 * 10 ** 7)
s, e = [1644076701048410800736598044521957621165075009220047353598695908154798545574669213628822983013478131645136107829991107147966592023064802684205984935604556580976432082255148549763, 13371337]
res = R.log2() * R(Integer(2) ** e) * R(s)
res = res - res.floor()
RR = RealField(10000)
res = RR(res)
res = RR(2) ** res

for i in range(70 * 8, 80 * 8):
    cc = int(res * RR(2) ** i)
    print(long_to_bytes(cc))