Efficient n-th division polynomial of elliptic curve

asked 2018-02-27 12:59:26 +0200

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

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2019-03-07 15:44:47 +0200

Sjoerder
1

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

add a comment

answered 2020-05-28 18:30:59 +0200

John Cremona
701 ●35 ●22

You can see how division polynomial is implemented using E.division_polynomial??. With just one ? you can see its parameters. The second optional paramater defaults to a variable x. The documentation (which I wrote, I think) says

 "x" - optional ring element to use as the "x" variable. If x is
 None, then a new polynomial ring will be constructed over the
 base ring of the elliptic curve, and its generator will be used
 as x. Note that x does not need to be a generator of a polynomial
 ring; any ring element is ok. This permits fast calculation of
 the torsion polynomial *evaluated* on any element of a ring.

i.e. in your code you could compute E.division_polynomial(N,z) for each z.

edit flag offensive delete link

add a comment

Your Answer

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

Add Answer

Efficient n-th division polynomial of elliptic curve

2 Answers

Your Answer

Question Tools

Stats

Related questions

Efficient n-th division polynomial of elliptic curve edit

2 Answers

Your Answer

Question Tools

Stats

Related questions

Efficient n-th division polynomial of elliptic curve