# Public key
p = int("0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff", 16)
n = int("0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973", 16)
a = int("0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc", 16)
b = int("0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
E = EllipticCurve(GF(p), [a,b])
Gx, Gy = int("0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16), int("0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f",16)
G = E(Gx,Gy)
q = int("0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973", 16)
E.set_order(q)
A = E(7879504150948819850549745883466444877682489323403501152869725364572188265375858123545016630176401541226148526800603, 31552960990834836689412952244211652821925770500774563624481531678327643118616074804953747852787762798874755480152768)

# Signatures
signatures = [(32826399720615272786552863579906732838828485153726088587917290670186739823304954089437981947662636986491185208292354, 26356473258516040355975223981874180986456304542718892989068625649552282094804), (1778132344415047181559309679808483514538902859422046220362430053972388674296950498597203641852700280164798493918992, 79448438017457428334213315806422344148161853972011266613345275709219917442957), (18257873623449013385461250375414409088906084159910898520110033721083191483775934570940870263345717196484432928480105, 19538869578297108730647338770763532959174643055974377672339748810885908204450), (964104784937218518189540942576122372605658618113224893444067019529040721839865187048708051270165678473146658554293, 90033161079826374822914574942447988387809592801981000152790870810271530628848)]

# HNP
N = 4
M = matrix(QQ, N+2, N+2)
B = 2^256

# Lattice
#   q
#       q
#           q
#               q                
#  e0  e1  e2  e3  B/q
# -r0 -r1 -r2 -r3  B
for i in range(N):
    M[i,i]  = ZZ(q)
    M[-2,i] = ZZ(signatures[i][1])
    M[-1,i] = ZZ(-signatures[i][0])
M[-2,-2] = 2^256/q
M[-1,-1] = 2^256

M_lll = M.LLL()
solutions = M_lll.find(lambda entry:entry==2^256,indices=True)

if solutions != {}:
    # Get solution vector
    solution = solutions.popitem()[0]
    solution = list(M_lll[solution[0]])
    x = (-solution[-2]*q/B) % q

    for x_i in range(x-10, x+10):
        if x_i *G == A:
            print(f"Found private key {x_i}")
            break