def long_to_bytes(data):
    data = str(hex(long(data)))[2:-1]
    return "".join([chr(int(data[i:i + 2], 16)) for i in range(0, len(data), 2)])
    
def bytes_to_long(data):
    return int(data.encode('hex'), 16)

def coppersmith(N,e,known_m,c,epsilon=1/50):
    P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
    pol = (known_m + x)^e - c
    roots = pol.small_roots(epsilon=epsilon)
    return roots

# N = int(sys.argv[1])
# e = int(sys.argv[2])
# known_m = int(sys.argv[3])     # known highbits
# c = int(sys.argv[4])
# epsilon = float(sys.argv[5])

# N = 81053193927250264783566985429154416138157147698823289494002979262797599465572687476790505031591391754013172670249618790973537153560390160860013099074549932727343396113580774573381416544774546969192899373152534956013486790573029621816421372182268101045756381729376715395654852235735600227757316988323789215801
# e = 3 
# known_bytes = 71048149665269701296041952343524576709919180708939192347457993594873839875881422138042268763117125417371401200734334938495476782483690674603363605219127097310912361368139675847802111050567822045157398185237833548924634202247500796241253912002443132785823203908519234762128525509105040251218444469483782143939
# m = 37062878937436962653995689028654250725736332269786388119471362520857826267922108490833593519181691929730913327699076784996142483960848520404883466241245269570612774357764788682733983116474986011828024560655992480980890622941039190736844622857068189444936220221809880193519052881348621412250204305900283769375
# unknown_bits = 35 * 8
# m = known_bytes << unknown_bits
# c = 9772611836823380427213548396439158859522530937451973879892473621719601100760446168810460223771061011761417326374817118535221248021594225929363541723867001473480164037142119648607299201376113133628271393349859081708391421530862128779136669063607845859426909209226573205671398944275610503008727106518952881445+6060

# def coppersmith(shiftbits, k):
F.<x> = PolynomialRing(Zmod(n))
invE = inverse_mod(e, n)
f = (s << shiftbits) + x + (k - 1) * invE   # make monic
x0 = f.small_roots(X=2 ** shiftbits, beta=0.44, epsilon=1/32)
    # return x0

# root = coppersmith(N,e,m,c,epsilon)

# root = coppersmith(N,e,m,c,epsilon)
print(root)

# [1024492081346868081681062631988023983415914300202458351981486544123228443840991558269]
# sage coppersmith.sage  18.57s user 0.84s system 98% cpu 19.638 total