Way back in December I spent some time looking at Elliptic Divisibility Sequences in connection with computing heights of points on elliptic curves. At the cryptography conference I recently attended, one of the talks presented a generalisation of EDS to higher dimensions described as elliptic nets. These too find application to elliptic curves- in the two dimensional case, allowing for computation of pairings. I’m hoping to look into these in more depth, and so they’ll probably crop up in later posts – but first I felt I should tie up some loose ends related to EDS.
At the time I’d been working with Maple, which proved unwieldy for working over number fields such as those discussed in Everest and Ward’s paper2. Further, I only got as far as implementing a special case of Shipsey’s algorithm for computing terms of such a sequence efficiently. SAGE’s object-oriented approach provides a vastly superior environment for algebraic geometry to Maple, which helped solve the first problem; and my mathematical understanding has progressed sufficiently to get to grips with the full version of Shipsey’s algorithm (and fill in the blanks necessary for an implementation).
So eds is a SAGE class for arbitrary Elliptic Divisibility Sequences. It’s pretty basic at present but fit for purpose- terms of the sequence are stored in a hash table, and when an as-yet uncomputed term n is requested the factors of n are compared to the known septuples to establish an efficient chain to the desired term from existing data. There’s still room for improvement here, however, as there are seven tuples containing the nth term of varying difficulty to compute, and there’s no attempt to compute some earlier tuples to speed things up further yet. These are both approaches I’d like to attempt before delving into the more general elliptic nets.
These are implementation concerns however, and shouldn’t alter interaction with the class, which I’ve hopefully made as simple as possible. As before, the working assumption is of a ‘proper’ EDS with leading terms 0, 1. Supplying terms 2, 3 and 4 is then sufficient to specify the entire sequence: initially the object is populated with the first eight terms. You also need to supply a ring of definition for the terms of the sequence so that SAGE doesn’t trip up- at least, until I find a way to determine this unambiguously from the input.
Using the class
The simplest example of an EDS is the integers themselves. So we can construct this EDS X with arguments 2,3,4:
sage: attach "eds.sage"
sage: X=eds(ZZ,2,3,4)
sage: X
EDS over Integer Ring with terms {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7}
Here I’ve attached the class, specified an EDS and asked for it back – at the moment, such a request gives you the ring of definition and all the currently-stored terms. Individual terms are extracted in the obvious way:
sage: X[7] 7 sage: X[25] Calculating via Shipsey Already have septuple with centre 1 , binary-chaining from there. 25 sage: X[32] Calculating via Shipsey Already have septuple with centre 8 , binary-chaining from there. 32
If a term is already known (such as the 7 here), it’s simply returned from the hash table. Otherwise, Shipsey’s algorithm (Thm 3.4.1 of her thesis1) is employed, after determination of a factor k to use as a starting block: for 25, as the tuple about 5 wasn’t known, the basic double-and-add has been employed; but for 32, the tuple about 8 allows for faster computation.
You can test for the existence of both individual terms and entire septuples within the hash table:
sage: X.has_element(32) True sage: X.has_septuple(32) True sage: X.has_element(35) True sage: X.has_septuple(35) False sage: X.has_element(38) False
In this case, both the 32nd term and it’s surrounding tuple are known; term 35 is known but not the tuple; and term 38 is not known at all.
EDS from elliptic curves- finding heights
Much of the interest in EDS arises from the fact that for a point P of an elliptic curve E, the division polynomials φn(P) are just such a sequence. These polynomials have the property that the zeroes of φn are the x co-ordinates of the n-torsion points, and feature in the explicit formulae for the group law on an elliptic curve; their computation is also of relevance to the SEA algorithm.
heights contains supplementary functions for constructing EDS with terms corresponding to the φn(P); technically you can specify an EDS with terms the φn themselves then evaluate for chosen P, but this is much slower and thus it is generally preferable to attach sequences to points rather than curves. The basic formula (21) from Everest and Ward2 then gives a means to estimate the height of the point; SAGE can easily make sense at runtime of the norm, degree of field extension and so on that are required.
For instance, their example 4 gives the curve y2+y=x3-x2 over K=Q(√ -2) and the point Q=(2+√-2,1+2√-2). We construct the curve and EDS (using EDSfromPoint) and recover a height estimate (based here on the 100th term of the sequence, using heightn) as follows:
sage: K=NumberField(x^2+2,'a') sage: a=K.0 sage: E=EllipticCurve(K,[0,-1,1,0,0]) sage: E Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 over Number Field in a with defining polynomial x^2 + 2 sage: Q=E([2+a,1+2*a]) sage: attach "heights.sage" sage: X=EDSfromPoint(Q) sage: X EDS over Number Field in a with defining polynomial x^2 + 2 with terms {0: 0, 1: 1, 2: 4*a + 3, 3: 11*a - 63, 4: -612*a + 689, 5: 17637*a, 6: -5055750*a - 4675301, 7: 2521168375*a - 4167504129} sage: time heightn(Q,X,100) Calculating via Shipsey Already have septuple with centre 4 , binary-chaining from there. CPU times: user 0.19 s, sys: 0.01 s, total: 0.20 s Wall time: 0.20 0.457448706299596
This compares favourably with Silverman’s accurate value of 0.45754…
Note that due to the scaling convention adopted, heights computed in this way will be half those computed by SAGE via PARI. However, PARI can only be used for curves defined over the rationals – with these procedures, it’s possible (to a low degree of accuracy) to determine heights for curves defined over number fields.
References
1: Shipsey- Elliptic Divisibility Sequences (Download)
2: Everest, Ward- The canonical height of an algebraic point on an elliptic curve. (MathSciNet entry) (Download [PS])
