Modulo Errors

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 paper². 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 thesis¹) 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 Ward² 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 y²+y=x³-x² 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])

A while ago I received a request for articles for a new magazine, iSquared, which seeks to cover mathematical topics, particularly real-world applications, at a level accessible to those not active in the field. This is quite a challenge, but a vital one. My own article, on the Prisoner’s Dilemma in game theory, appears in the first edition, so you can judge how well I did by buying a copy! I suspect I went overly-technical, but it’s a long time since I was an A-level student- although I remember reading New Scientist then and I don’t think the content is any more demanding in iSquared. Certainly I feel any scientifically literate undergrad with an interest in maths would find it rewarding, and at £10 for the year, educators have little to lose by picking up a subscription for a college library. For those of you more deeply involved in the subject, why not consider writing an article? Whichever category you fall into, please give it your support!

I’m not sure how many UK readers I have, and this blog isn’t normally used for personal stuff, but if I’m going over the side of a bridge I want to raise as much money as possible- so I’m crossposting this pretty much everywhere!

For reasons I’m not entirely sure of, I’ve agreed to abseil off the Forth Rail Bridge on behalf of the children’s charity, NCH. This will apparently involve 165ft of ‘SAS style (free fall)’ action- that’s 50 metres, or roughly the height of a 14 floor building (according to my favourite architect). It’s probably worth pointing out that I’ve never abseiled before… but it’ll be from one of the towers at the shore, rather than plunging into the waters of the Firth of Forth.

So yes, this is your chance to pay me to go jump off a bridge. Or rather, raise money for some of the most vulnerable children and young people in Scotland. Every little helps- so if you’d like to sponsor me, leave a reply / email / e2msg / facebook message / find me in JCMB 4607. The event is scheduled for Sunday October 21st, with my turn being bright and early at 9:28. Weather permitting: which is to say, they’ll re-arrange for high winds, but not rain.

(Practical bit: UK citizens who pay income tax can gift aid their donation, allowing the tax to be reclaimed by NCH- I’ll need your address for that. You can donate direct to me by cash (sterling / euros), personal cheque (sterling) or paypal (grudgingly as they take a cut)- I’ll then write a single cheque to NCH. Easy!)

Current Status: Over £200 raised- abseiling tomorrow!