# partial_d.sage

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    P = var('P')

    for k in range(1, e+1):
        print(k)
        results = solve_mod([e*d0*P - k*(n-P+1)*P + k*n == P], 2^kbits)
        print(results)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    print("start!")
    N = 124588792854585991543122421017579759242707321792822503200983206042530513248160179498235727796077646122690756838184806567078369714502863053151565317001149999657802192888347495811627518984421857644550440227092744651891241056244522365071057538408743656419815042273198915328775318113249292516318084091006804073157
    e = 109882604549059925698337132134274221192629463500162142191698591870337535769029028534472608748886487359428031919436640522967282998054300836913823872240009473529848093066417214204419524969532809574214972094458725753812433268395365056339836734440559680393774144424319015013231971239186514285386946953708656025167
    gift = 870326170979229749948990285479428244545993216619118847039141213397137332130507928675398<<120
    enc = 67594553703442235599059635874603827578172490479401786646993398183588852399713973330711427103837471337354320292107030571309136139408387709045820388737058807570181494946004078391176620443144203444539824749021559446977491340748598503240780118417968040337516983519810680009697701876451548797213677765172108334420

    # n = 89820998365358013473897522178239129504456795742012047145284663770709932773990122507570315308220128739656230032209252739482850153821841585443253284474483254217510876146854423759901130591536438014306597399390867386257374956301247066160070998068007088716177575177441106230294270738703222381930945708365089958721
    #n = 22886501935336065182326527443310749425171647238626282413401383196346489429704102057721649923432485366546493527638108629871871958769468030807810941317738572491741321770829422490153900877578213060028200750443514516859983684513695362081632707707911149834332602372979434088912942912851938670551379551225494633726058082769820094808639196295355917935311972995448897110349031393317379557438029524114635337222762331676438910234927812848930884968824910365642189803231791506971024009754951423293404469711697860605662568095139192065818762238142932255427846376827236900905886912090980882932064525237833246818119279930638745034749
    e = 109882604549059925698337132134274221192629463500162142191698591870337535769029028534472608748886487359428031919436640522967282998054300836913823872240009473529848093066417214204419524969532809574214972094458725753812433268395365056339836734440559680393774144424319015013231971239186514285386946953708656025167
    # nbits = n.nbits()
    # kbits = 508
    d0 = 870326170979229749948990285479428244545993216619118847039141213397137332130507928675398<<120
    # d0 = 34853327299025755595075304279734536658859779367199829099864542202921236791274445811280627334793831109517046902319361193799141879670245490634859470527482992704459154837275611693065523725040305710310173322460987652380350573853183919952409167226508053603975272068685866320882516555872353263491319823526487495001
    # print("lower %d bits (of %d bits) is given" % (kbits, nbits))

    p = find_p(d0, 120, e, N)
    print("found p: %d" % p)
