Ask Your Question
0

Efficient n-th division polynomial of elliptic curve

asked 2018-02-27 05:59:26 -0500

anonymous user

Anonymous

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?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2019-03-07 08:44:47 -0500

Perform these two steps at once:

    F = E.division_polynomial(N)
    ...
        z = F(x)

By passing x to division_polynomial. Make sure that x is in the field R, and move the line after where x is defined:

z = E.division_polynomial(N, R(x))

With this change, your program runs within 2 seconds on my computer.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-02-27 05:59:26 -0500

Seen: 117 times

Last updated: Feb 27 '18