solve.py

from sage.all import *

# Curve: y^2 = x^3 + ax + b (mod p)
p = 404993569381
P = (391109997465, 167359562362)
Q = (209038982304, 168517698208)
b = 54575449882

# Retrieve a
x, y = P[0], P[1]
a = QQ(y**2 - x**3 - b)/x % p

F = FiniteField(p)
E = EllipticCurve(F,[a,b])
factors = list(factor(E.order()))
print(factors)

# Attack
P = E.point(P)
Q = E.point(Q)
primes = []
for num in factors:
    primes.append(num[0]**num[1])
dlogs = []
for fac in primes:
    t = int(P.order()) / int(fac)
    dlog = discrete_log(t*Q,t*P,operation="+")
    dlogs += [dlog]
d = crt(dlogs, primes)
print(d, d*P == Q)