I try to implement the algorithm described in sec. 4 of this paper: https:// eprint.iacr.org/2002/109.pdf. Currently I have the following code:
N = 1444329727510154393553799612747635457542181563961160832013134005088873165794135221
js = [(-2^5)^3, (-2^5*3)^3, (-2^5*3*5*11)^3, (-2^6*3*5*23*29)^3]
R = Integers(N)
B1 = B2 = 10
for j in js:
a = R(j)/(R(1728)-R(j))
cs = [random.randint(1,N) for _ in range(B1)]
xs = [random.randint(1,N) for _ in range(B2)]
for c in cs:
E = EllipticCurve([3*a*c^2, 2*a*c^3])
F = E.division_polynomial(N)
for x in xs:
z = F(x)
if gcd(z,N) != 1:
print(j, c, x, z, gcd(z,N))
I think it is correct, but the division polynomial computation runs forever, while the paper claims it finishes in seconds because every operation is modulo some integer (sec. 3). It also uses dynamical programming and I don't know how division_polynomial is implemented.
How can I do this more efficiently in Sage?
