Midnight Sun Finals 2019 - RZA2

solve.sage

from Crypto.Util.number import *

n = 118173998641659433141031218423093267548048945830460552160732748274571974743297930821423113390029083098858035838064885829588967199550126084897009304331836294104589302387252278933370240317467378376797843379485665856003112996215247651060003047081838833325054418881162956647931078011461049685774070539302432802113792476309961767049580409488915273417272971605423056480946448420246170538977427027687185230659802277819960185028241326766028592105200802992171
a = 47702774091583083413514954181005338733744246354146014100833529117112767
c = 12568593503732225284833930665556838287412199439692821417647372971869231723559992154443706678410038339647264823124946805716114186285024175170040286493705539280834058460961400557745983656762142889655126327977159776509025806614615683229732063597008220981903454189924787333897642661119487550976064177525965960903757425676552365701751129959682193371999227133565308776511273796468549993234547730548169945552741777405821627017605337784463424463117997971328
e = 65537

guess_x = int(isqrt(n)/a) - 2**277
F.<x> = PolynomialRing(Zmod(n), implementation='NTL')

for i in range(1000):
    f = ((guess_x + x) * a + i)
    f = f.monic()
    roots = f.small_roots(X=2**277,beta=0.4)
    print i, roots
    for root in roots:
        p = int((guess_x + root) * a + i)
        q = n/p
        assert p * q == n
        d = inverse_mod(e, (p - 1) * (q - 1))
        print repr(long_to_bytes(pow(c, d, n)))
        exit()

# midnight{tumbleweed_tumbleweed_tumbleweed}