Modulo Errors

As a companion to my previous post, here’s the list of valid forms of a connected maximal cyclotomic graph with an entry from the ring of integers of Q(√ -7):

Uncharged Lines:

Uncharged Squares:

Uncharged Hexagons:

Uncharged Cubes:

T_2k Variants (Infinite Family):

A chain of the form

for any integer k.

Charged Triangles:

Charged Squares:

or

C_2k Variants (Infinite Family):

A chain of the form

for any integer k.

To recap: I’ve been trying to completely classify the possible matrices/graphs subject to a constraint on their eigenvalues we’re describing as cyclotomicity. This is a problem that can be posed in the ring of integers of any imaginary quadratic extension field, but for all but finitely many of them reduces to the problem in the rational-integer case which has been solved in a paper by my supervisor.

For a couple of the remaining fields, the problem is easy: there’s only a finite supply of graphs featuring a non-rational integer label, which can be found simply by running a growing process to termination. But once you move to fields with norm 2 integers, there’s enough freedom for things to get interesting: I’ve been working in the rings of integers of Q(√ -2) and Q(√ -7), where I can demonstrate an infinite family of such graphs and so the growing algorithm can never terminate. Nonetheless, in the simpler, ‘uncharged’ version of the problem, I have (proven) a complete classification in both of these fields. With a bit more work I’ve now settled the general case in Q(√ -2) and expect the logic of the argument (although not the precise results) to carry over to Q(√ -7).

That argument is essentially a lengthy case analysis; rather than get into the details I thought I’d just present the ‘zoo’ of possible graphs. The forms presented are necessary conditions (any cyclotomic graph will take one of these forms) but not sufficient (there may be non-cyclotomic graphs satisfying the form). However, no form contains no cyclotomic graphs - for a given form, including any instance of the infinite ones, I can exhibit at least one class of cyclotomic graphs.

After applying a numbering, the visual styling of an edge between two nodes i<j indicates the norm of the edge label (entry [i,j] of the matrix; take the conjugate for entry [j,i]); uncharged nodes are indicated by a point whilst [C] denotes a charged node (value of ±1 for entry [i.i] if node i is charged, otherwise zero). The precise choice of labels and charges requires some care over signs to ensure that the matrix has minimal polynomial x²-4; working with forms saves tracking such details, choosing equivalence class representatives, etc.

Then for the ring of integers of Q(√ -2) any connected maximal cyclotomic graph with a non-rational integer label must take one of the following forms:

Uncharged Squares:

Uncharged Cubes:

T_2k Variants (Infinite Family):

A chain of the form

for any integer k.

Charged Triangles:

Charged Squares:

or

C_2k Variants (Infinite Family):

A chain of the form

for any integer k.

As I said, I expect this to easily generalise to Q(√-7); the remaining fields Q(√-1) and Q(√-3) present more of a computational challenge, but meeting that challenge will hopefully be rewarded with more interesting behaviour!

So it’s been over two months since a post; more attentive readers will have noticed that there was one, but now there isn’t. I’ve moved away from thinking about cryptography to generalising some number/graph theoretic results of my supervisor, concerning matrices with constrained eigenvalues. However, this creates a problem: unless I ‘blog every up and down of the research process (which could be interesting, but would slow me down!) information on here becomes decreasingly accurate or relevant as I revise my thinking on the topic. Certainly it would be premature to present firm results at the moment.

But I can at least set the stage for more technically-minded readers (a friendlier explanation/illustration will hopefully follow once I truly understand all this!). Chris has characterised all symmetric integer matrices with the property that their eigenvalues are at most 2 in modulus; under a suitable transformation of their characteristic polynomials, these give cyclotomic polynomials and thus are referred to as cyclotomic matrices. Conveniently, any submatrix of a cyclotomic matrix is itself cyclotomic, so it suffices to find maximal examples. Although there are infinite families of these matrices, there are only a few ‘types’ possible.

These types are best understood by considering not the matrix, but an associated graph, where values in the matrix determine the weights on edges and nodes of the graph. This introduces a notion of equivalence, since many matrices will correspond to the same graph or certain well-defined variations on it. Further, we can adjoin nodes and edges to the corresponding graph to try and ‘grow’ towards maximal examples.

The motivation comes from finding polynomials of small Mahler measure- whilst a cyclotomic polynomial has measure 1, all others seem to be pushed away, with the smallest known value being 1.176… The question is how to generate small examples, and these matrices provide a way: by adjoining a single extra node to a maximal cyclotomic graph, a non-cyclotomic graph/matrix is obtained and thus a non-cyclotomic polynomial. The minimal graphs with this property (non-cyclotomic, but all subgraphs cyclotomic) often correspond to polynomials with some of the smallest known Mahler measures.

But some examples are not generated in this way, which is where I’ve stepped in. There is no reason to restrict attention to integer matrices, and I’ve established which imaginary quadratic extensions of the rationals give rise to rings of integers over which suitable matrices can be found. For a couple of fields, there are very few new (non rational-integer) cyclotomic matrices, and I have a complete description of them, but in others there are again infinite families as well as occasional examples that don’t generalise.

So I explore this behaviour by growing graphs/matrices, and try to spot patterns as they emerge from the fragments. I use the university’s parallel computing cluster Eddie for brute force work in SAGE, but such is the nature of the combinatorial explosion that even this doesn’t suffice without some mathematical insight along the way, as I try to refine my growing algorithms and capture equivalence as early as possible. I’m hopefully nearing the point where all examples fit into known families, at which point I’ll need to switch into serious mathematician mode and try and prove why this should be so. But for now I need to make sure that nothing unexpected tumbles out of each batch of calculations!

On a completely unrelated note, I’ve dragged modulo errors up to date with wordpress 2.5 and switched themes; please shout if you find I’ve broken something along the way.

I promised some of my tutorial students a demonstration of how the ‘highschool’ approach to Euclid’s algorithm can be reversed to give rise to the extended Euclidean algorithm - as opposed to the version in their lecture notes, which finds both gcd(a,b) and x,y such that ax+by=gcd(a,b) in one pass, at the price of some notational complexity. To do so, it seemed worth recapping some of the properties of divisibility that make Euclid’s algorithm tick, and give an application for its extended form. That ended up taking four pages, so I figured I’d post it here as well… you can read it behind the cut, or download the LaTeX-formatted pdf version.

Read the rest of this entry »

Suppose you have a rule for addition of some objects (most generally, elements of a semigroup), and you wish to compute the sum of n copies of the same object. How could you achieve this?

The primary school answer is to do just that: given g, compute 2g=g+g; then compute 3g=2g+g and so on, for n steps. But this rapidly becomes tedious, and isn’t (I hope) how we’d perform such a calculation in our heads: instead, we’d try to take bigger jumps. For instance, to compute the number 16g, we can find 2g, add that to itself to reach 4g, and again for 8g, hitting 16g after just 4 steps. Had we wanted 17, we’d then just add g again.

The sequence of intermediate values correspond to an addition chain for n: this is a sequence starting at a₀=1 and ending at a_l=n with the property that for any term a_k there exist terms a_i,a_j with a_k=a_i+a_j. That is, every term is the sum of two earlier terms (not necessarily distinct), so we can reach ng by computing each a_kg in turn without needing anything fancier than our addition law.

As a side effect, an addition chain also tells us how to exponentiate if we know how to multiply, since x^a+b=x^ax^b so we can build up to xⁿ by finding the powers x^a_k in turn.

Thus our tedious sequence for 16 is 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16, with the more sophisticated one being 1,2,4,8,16. If I asked you to compute 16x for a number x, you’d probably do something different: compute 10x (easy in base 10!) and 6x, then add those. With access to a multiplication procedure, this is definitely more efficient: but without that luxury it can still be used to give an addition chain for 16, by finding chains for 10 and 6. These are 1,2,4,5,10 and 1,2,3,6 respectively, so we can merge them into the chain 1,2,3,4,5,6,10,16.

We describe the length of the chain as l: that is, there are l terms after the 1. Notice that at worst, therefore, we need n-1 terms. If we move as quickly as possible by taking a_k+1=a_k+a_k=2a_k then the greatest value we can reach after m terms is 2^m, as demonstrated with the chain for 2⁴=16. However, if we can compute n and m in l_n,l_m terms, it needn’t take as many as l_n+l_m+1 terms to compute n+m, since there may be common terms in the chains. Finally, as defined an addition chain needn’t make use of all it’s terms: for example, 1,2,4,6,8,16 is still a chain for 16, although the 6 isn’t needed. We will obviously be interested in chains without any such wasted terms.

The observation for powers of two motivates a first attempt at an efficient algorithm for building addition chains. if n is 1, then we have nothing to do: the chain 1 suffices. Otherwise, we can work recursively: for an even number n=2k, we ask for the chain for k and then add 2k to the end; whereas for an odd number n=2k+1, we ask for the chain for k and add 2k then 2k+1 to the end. This will require at most log₂n calls, and each step adds 1 or 2 entries to the chain.

This can also be captured by considering the binary representation of n, which will also indicate whether we hit an even or odd number at each stage. Suppose n is of the form

where each d_i is either 0 or 1, and d_k=1 so there are no leading zeros. Then we start the chain with 1, and read from left to right, ignoring the leading 1: if we see a 0, then we double the last term of the chain; if we see a 1, add 1 to this new term as well. More formally:

Input: the binary expansion of n.

Output: an addition chain for n.

Set a₀=1
Set t=1
for i from k-1 down to 0:
    Set a_t=2a_t-1 and t=t+1.
    If d_i=1:
        Set a_t=a_t-1+1 and t=t+1
return a₀…a_t

For instance, with n a power of 2 we will see only a run of zeros, and thus perform the appropriate number of doublings, for a chain of length log₂n. For n one less than a power of two, the expansion consists entirely of 1s, costing 2log₂n. For an ‘average’ number where each digit has around a 50% chance of being a 1 or a 0, the chain will therefore be of approximate length (3/2)log₂n. More formally, we can define the Hamming Weight v(n) to be the number of 1s in the binary expansion of n; then the chain will have length floor(log₂n) + v(n) -1.

Is this optimal? A counterexample suffices to show it is not, the first being 15, which is 1111 in binary. Using the binary expansion we get the sequence 1,2,3,6,7,14,15 of length 6 (=3+4-1 as claimed). But the sequence would be 1,2,3,5,10,15 of length 5 and hence 1 shorter.

Nonetheless, our binary chain gives a much better upper bound than the naive chain of (n-1) steps, and is very simple to implement both in logic and memory. The idea also generalises to arbitrary bases, as follows.

Suppose n is of the form

where each d_i is in the range 0…m-1, d_k non-zero. Then we can compute an m-ary addition chain for n:

Input: the m-ary expansion of n.

Output: an addition chain for n.

Set a=0
Start the chain with 1,2,3,…,m-1.
for i from k down to 0:
    Extend the chain to m*a (if not already present) and set a=m*a.
    Add a+d_i to the chain (if not already present), and set a=a+d_i.
return chain.

Notice that a tracks the last term computed, and that extending the chain to m*a is itself an addition chain problem: this makes some 2^k a good choice for m, since this extension can then be accomplished in k additions.

The shorter chain for 15 arises from its ternary expansion: considered as (120)₃ 1*9+2*3+0*1, we have an initial chain of 1,2 then apply the loop. With a=0,d₂=1 we set a=3a=0 then a=a+1=1; neither of these need to be added to the chain; for a=1, d₁=2 we set a=3a=3 which requires the addition of 3 to the chain; then a=a+2=5 which extends the chain to 1,2,3,5; finally for a=5,d₂=0 we set a=3a=15, adding first 10 then 15 to the chain; then a=a+0=15 so we terminate with chain 1,2,3,5,10,15.

The optimal choice of m depends on n, since although there will be less steps (log_mn) for greater m, each step will require more additions in the computation of m*a. Nor are m-ary expansions the end of the story- there are various other tricks available to finesse addition chains. However, there is no known algorithm for finding shortest addition chains- and a generalisation of the problem to finding shortest addition sequences (chains that contain a desired list of values n₁,n₂,…,n_k) is NP-complete. Searching for short chains is therefore an interesting challenge, and is constrained by the fact that unless you are precomputing them for future use, any shorter chain must offer a speedup in computation greater than the time taken to find it.

There are, however, bounds for the length of the chain:

Where v(n) is the Hamming weight as before.

However, if you have access to basic operations other than addition, all bets are off. In some contexts (such as elliptic curves), finding the inverse of an element is easy and so we can achieve subtraction, giving rise to addition-subtraction chains. For the pairing computations I’ve been interested in, I’ve never actually described a block addition. It is possible, following an algorithm of Shipsey, to do so, although it is much more expensive than the block double. But even if it cost no more, and we had an oracle for optimal chains, such an approach would only rarely beat the current algorithm. This is because access to the double-add procedure makes the Hamming weight irrelevant: for instance, with 15 we could form the chain 1,3,7,15. This means that we can compute in log₂n block operations, and comparing to the lower bound for addition chains above shows that this is almost always better.

Still, ideas from addition chains can motivate construction of other operations: access to triple, tripleadd and tripleadd2 procedures would allow for chain of log₃n length, although it is likely that these block operations would be more expensive than the double and doubleadds. Even if they don’t turn out to be useful for my work, the subtleties of this innocent-looking problem still makes for interesting mathematics!

References/Further Reading

Knuth- The Art of Computer Programming Vol. 2: Seminumerical Algorithms.

Bos and Coster- Addition Chain Heuristics in Advances in Cryptology- Crypto’89 (Lecture Notes in Computer Science) (Available via SpringerLink.)

Gordon- A Survey of Fast Exponentiation Methods. (Available via citeseer.)

As always in mathematics, when something turns out to be useful, it’s worth asking whether it can be generalised to a broader setting. For Elliptic Divisibility Sequences, that generalisation is Elliptic Nets. For a free abelian group of finite rank, this is a function W satisfying the condition:

for any p,q,r,s from the group.
(EDS are then recovered as the special case where the chosen group is the integers).

The theory of elliptic nets has been developed extensively by Katherine Stange, and the papers/presentations from her website provide a wealth of information. I’ve been writing a SAGE implementation of her results, from which we need a few key ideas.

What’s remarkable is that it is not just that sequences can be generalised to arrays: the connection to elliptic curves is also preserved. That is, given n distinct points of an elliptic curve, there is a rank n elliptic net corresponding to those points. The terms of the EDS corresponding to each point will appear in the array, but more complicated interactions of the points are also captured. In the rank 1 case, it was possible to estimate heights purely by manipulation of terms of an EDS; in a similar way, routine manipulation of elliptic nets allows for computation of the Tate pairing.

The use of pairings is currently a hot topic in cryptography, with both destructive and constructive applications. The Tate Pairing allows pairs of elements of an elliptic curve group to be mapped to a finite field. In certain cases, and provided the pairing can be computed efficiently, this transplants the Discrete Logarithm Problem (DLP) into an easier environment, thus weakening the cryptosystem. On the other hand, the gap in difficulty between the two DLPs can itself be used to design cryptosystems and protocols, such as Identity based cryptography.

For the theoretical background, I recommend again Stange’s work. The take-home message however, is as follows:

• For a point P of order m on an elliptic curve E, to compute the pairing of P with itself it suffices to recover terms m+1 and m+2 of the EDS associated with P.
• For distinct points P,Q on an elliptic curve E with P of order m, to compute the pairing of P with Q it suffices to recover elements (m,0) and (m,1) of the elliptic net associated with P and Q.

Thus I have been interested in the sequence/net calculations necessary to recover these quantities. Notice that it is not necessary to compute general (i,j) elements, but only the rows (i,0) and (i,1). The former is in fact the EDS associated with P. Like Shipsey’s algorithm, Stange presents a double-and-add algorithm for the general case of reaching elements (m,0) and (m,1) via successive blocks of elements. For details on this, a possible refinement of my own, and a SAGE implementation, see the next post. This would solve the first problem as well, by choosing a random Q, but the (i,1) terms introduce an unnecessary overhead. Eliminating this gives rise to an alternative to Shipsey’s algorithm for EDS, so I’ve implemented this case separately with an equivalent interface to my existing eds class. It’s unclear which approach is preferable where (although Stange’s is almost definitely the one to use over finite fields), so I hope to furnish both with equivalent functionality and compare their performance for height computation (details to follow). Finally, the wrappers to move from points to nets and compute pairings have been implemented, although I need a lot more test cases to identify potential shortcomings! Ultimately, I’d like to bundle all these ideas together into a more friendly, rank-aware elliptic net class for both roles (heights and pairings).

Last time, I gave some procedures to generate an elliptic divisibility sequence from a point of an elliptic curve, the motivation being that the growth rate of the sequence corresponds to the height of the point- and thus we can compute heights by computing terms of the sequence.

But what about going the other way? Given that we seek points of low height, can we search more intelligently by crafting sequences with a small growth rate, rather than simply mapping from (typically uninteresting) random points to their sequence? The easiest way to achieve this would be to start from the sequence, rather than from the point- but that requires a means to recover the point from the sequence.

Fortunately, Ward’s Memoir¹ provides just such a technique, although presented in terms of elliptic functions (the complex analysis way to view elliptic curves). Recall that to define a sequence, we need only specify the second, third and fourth terms h₂, h₃ and h₄. Then the corresponding point is (X,Y) on curve E: Y²=4X³ -g₂X -g₃, given by the following unpleasant formulae:

However, these needn’t be integral, and it’s preferable to rescale to eliminate that X³ coefficient. Fortunately both of these problems can be solved by clearing denominators, leading to a more pleasant representation of the point and curve. My basic algebra being as rusty as it is, this procedure me a surprisingly long time to figure out in the general case, but I have now added suitable features to my eds SAGE class. For such an object X, a call to X.ward_point() will return a point of an elliptic curve: you can extract the curve from a point P in SAGE by P.curve(). There’s a slight issue in that an EDS may define a singular curve: I’ve caught this exception, and in such a case you’ll get back the integer zero instead. I needed this to prevent large searches over EDS from crashing when such a sequence arose from the parameters, but it’s a bit of an ugly solution.

Given a method to turn sequences into points, the obvious question is whether it acts as the inverse to the creation of sequences from points. The answer turns out to be, almost! Extra scaling factors creep in to the sequence terms each time you loop through a cycle of EDS→point→EDS. The larger the terms, the greater the time/space requirements for manipulation of the sequence; this also has a knock-on effect on the approximate height computed. However, this can be fixed for curves over number fields: considering field elements as polynomials, rescaling each of h₂,h₃,h₄ to have content 1 recovers the original EDS. I offer no mathematical justification for this other than that it works! Thus heights now also includes EDSfromPoint_nf to generate EDS by just such a scaling.

Armed with these techniques, it’s now easy to generate curves of moderately small height that would otherwise be presumably difficult to stumble upon: for instance, with u=1+√2, the curve over the number field Q(u) given by y²=x³ + (-432u-864)*x + (-1728u+6480) has a the point (24-12u,108) of height around 0.0107. This unlikely looking curve arises from the much simpler EDS with defining terms -1,u-1,2u-2, found after a search over sequences from K with small terms that took about an hour. Considering how easily it was found, this compares favourably to the lowest known height over Q of about 0.0045. However, in the context of the Elliptic Lehmer problem heights should be scaled by the degree of the field extension, so to set a record a value of around 0.002 is needed for quadratic extensions such as K. So the search continues…

References

1: Morgan Ward- Memoir on Elliptic Divisibility Sequences (MathSciNet entry)

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])

Tomorrow I give my first year presentation, which determines whether I’m allowed to continue my studies. At 20-30 minutes, it’s a rather condensed version of my recent geometry club talk on the point counting problem, although this time I’m skipping more quickly through the fundamentals so that I can discuss some of the algorithms in depth, and taking a (hopefully) clearer route.

Both the report itself and the OHP slides version are available (pdf). Content covered: hyperelliptic curves, points, divisors, mumford polynomials and the Picard group/Jacobian; the discrete logarithm problem; explicit group law computation; characteristic polynomial of Frobenius and Weil theorems/interval; group-theoretic approaches; Schoof’s algorithm, SEA in genus 1, genus 2 hybrid algorithms.

Today I spoke at the Geometry Club about the use of hyperelliptic curves in public key cryptography. You can find my slides here, although they were supplemented by some boardwork that you’ll have to figure out from my other postings!