Modulo Errors

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!

The plaque marking the discovery of the quarternions, Dublin.

I’ve spent the last three days in Dublin, and whilst there I couldn’t resist taking a rare opportunity for mathematical tourism. Hamilton figured out the structure of the quarternions in “a flash of genius” during a morning walk along Dublin’s royal canal, carving them into the nearby Brougham bridge. Whilst the carving does not survive, there is a plaque at the spot to mark this discovery, and it was that I set off to see.

Getting there doesn’t seem too difficult, though: I got the 120 bus from Parnell Street (conveniently close to my hotel on Parnell Square) to Broombridge road. This is the opposite of advice found elsewhere online, but the suggested 20 route doesn’t seem to exist any more. If you have a map, it’s easy enough to follow the bus route, but as I didn’t I just asked the driver to give me a shout when we got there. Brougham is pronounced broom, so all you need to do is to find where Broombridge road crosses the canal and (it turns out) railway tracks: presumably taking the western suburban line would be an even easier way to get there, as the platform is next to the bridge. Of course, I went the wrong way along Broombridge road, which is easily detected by reaching the end without finding a bridge!

It’s been described as “the least visited tourist attraction in Dublin”, partly because the area isn’t particularly appealing today but presumably because there aren’t that many mathematical tourists!

It does seem a shame that the site - and Hamilton - are so overlooked compared to the attention that, say, local authors or artists get. But it’s better than nothing, as mathematical tourist attractions are few and far between, especially outside of universities. The bridges of Königsberg are often suggested; I’d also be fascinated to tour Japan in search of sangaku. If you have other ideas, why not mention them in the comments?

Welcome to the sixth edition of the Carnival of Mathematics! I’ve certainly enjoyed looking through this fortnight’s submissions, and hope you will too.

Trivium Pursuit’s series on when best to introduce formal arithmetic to children continues with this article, setting out their arguments for providing an informal experience of mathematics before the age of ten. I remember plodding through worksheets at that age, where “harder” simply meant “more tedious”, perfoming larger calculations with by-then familiar processes; it’d be interesting to know how my mathematical career would have been shaped by avoiding such drill in favour of the suggested approach. I suspect most mathematicians will also find it a very strange idea, assuming they also took to formal arithmetic at a very young age and thus find it hard to imagine struggling with such material.

Of course, the beauty of mathematics often lies not in getting an answer, but getting there in a clever way. Political Calculations presents criss-cross multiplication; an easier way to multiply two digit numbers in your head; whilst Let’s play math offers some guidelines for K-12 students to help organise their thoughts in problem solving. But over in the universe of discourse, Mark Dominus warns of the danger of over-thinking a problem where brute-force may suffice. This is particularly true when computers are thrown into the mix, as the time taken to devise and program an elegant solution may well exceed the runtime of the naive approach.

At the other extreme, though, there are computations which you wouldn’t survive to see the result of if you took the brute-force option. I’m reminded of this e2 writeup, which describes a particularly daft hello world program along with a curious question: if hardware performance continues to double with Moore’s law, how long should you wait before running such a program? After all, if you estimate a function will take 4 years to execute on your current machine, but one twice as fast will be available in 18 months, then you can save 6 months (and a load of electricity) by waiting a year and a half, obtaining the faster kit, and running your program for just two years. Conversely, if you want to guard against brute-force attacks for a given length of time, just how good does your encryption have to be?

Also on e2 (hey, if I’m hosting, I can plug my favourite site, right?), sam512 has been exploring very, very large numbers, inspired by this edition of xkcd: so far the clarkkkkson, hyper operator and linear array notation have been covered.

Many of this weeks submissions presented problems, of varying difficulty. As a warm-up, Sharp Brains‘ new puzzle master offers a brainteaser entitled ‘Party For Polyglots’. More demanding are two entries from MathNotations, aimed at calculus students: the first concerning properties of the ellipse, the second, more advanced post is on exploring infinite series. We close with the most amibitious material, the Unapolagetic Mathematician’s examination of the knot colouring problem: for the background, see here; this week’s submission explains what’s going on. I feel that I had an unfair advantage since my flatmate is a knot-theorist; I’m often intrigued by the techniques applied to this field. Plus I rarely get to draw pictures during my own research!

Thanks to all who submitted content, and to those of you reading this! The next stop for the carnival is Nonoscience, on the 4th of May.

Update 4/v/07: I’ve switched from Cantor’s definitions for a curve of the form y²=f(x) to a more general form, following the notation of a paper by Tanja Lange; that also describes many efficiency gains for these calculations, none of which I have yet adopted… I’m also implementing these procedures in SAGE, which seems a more natural environment. So consider all genus 2 stuff as work in progress!

jac is an implementation of the group law on the jacobian of a genus 2 hyperelliptic curve over a finite field, to work with the generic_group procedures described previously. Standard version is for Maple 10; you can also get a version for Maple 9, but this may not be updated as frequently.

An arbitrary divisor D is now either a list [a(u),b(u)] or the identity element zero. Addition of two such divisors D,E is given by g2JacGroupLaw(D,E) whilst g2JacMinus(D) gives the inverse. So these functions can be used as arguments for ncopies and so on. To set up the worksheet, specify a characteristic p; a degree five monic squarefree polynomial f(u) and a polynomial h(u) of degree at most 2. Only rational divisors and prime fields seem to work: working mod p generates sufficiently ugly Maple code to discourage me from trying extension fields there.

Also included are a couple of ways to get random divisors to compute with. randomDiv is incredibly slow as it naively tests random choices of a (monic quadratic) and b (linear) for suitability (that is, a dividing b^2+bh-f). randPoint(f,h) is smarter (transforming to y²=g(x), using the legendre symbol to test random choices of x for square g(x) then finding a root and transforming back to a suitable y) and of course you can combine two points into a weight 2 divisor using the group law.

Order computation, even with BSGS, becomes very slow for less than staggering values of p: this is of course the point cryptographically! For instance, it took my university workstation about 11 hours to find the order of a randomly constructed divisor from a curve over a field with around a hundred-thousand elements.

Last time I introduced the idea of divisors on a curve; but an observant reader may have noticed that along the way the idea of rational points seemed to be lost. Further, whilst the Riemann-Roch theorem guarantees that a divisor from the jacobian will have a reduced representative, no indication was given as to how that representative is to be found. In this post I’ll try to clear up both of these issues.

Recall that a semi-reduced divisor D from the jacobian takes the form (Σ_i^rP_i) - r∞ where the P_i are points (x_i,y_i) of C. We will represent this by a pair of polynomials D=div(a(u),b(u)) with the following properties:

such that b has degree less than that of a, and the appropriate multiplicity for repeated points- i.e., if P_i occurs k times in the semi-reduced representation of D, then (u-x_i)^k divides b-y_i. This ensures uniqueness.

The empty divisor (zero element of the jacobian) is denoted by div(1,0); if a is linear (and hence b constant) then the divisor corresponds to a single point of C; for the point (x,y) the divisor is div(u-x,y). The degree of a is described as the weight; ‘most’ reduced divisors will be of weight g. Recall that the co-ordinates of a point were only required to be in A rather than K; we describe a divisor as rational over K if the coefficients of a and b are from K. Beware that a rational divisor may therefore be the sum of points which are not K-rational points of the curve; however, a weight 1 rational divisor obviously corresponds to a K-rational point.

The K-rational principal divisors of C are a subgroup of P₀ and their image in J, J_K, the subgroup of rational divisors of the Jacobian, is the object of computational interest. The K-rational points of C are then identified with a subset of J_K; namely the divisors of weight at most 1; except in genus 1 (where they are J_K), this isn’t a subgroup due to the lack of closure.

So we wish to work with rational divisors from J_K.Given such divisors of the form div(a,b), it is undesirable to construct their sum by ‘unpacking’ the points P_i and forming new polynomials as the co-ordinates (roots of a, evaluations of b) might not be from K but A. Fortunately, it is also unnecessary: the only complications are connected to repeated points or the combination of a point and its negative; careful manipulation of gcds allows for direct computation of the semi-reduced form. See ¹ for details, which also describes moving from semi-reduced to reduced form. To do this, note that for a divisor D=div(a,b), the divisor E=-((b-v)-D)=div(a’,b’) is equivalent to D with deg(a’)=max(2g+1,2)-deg(a); thus by repeated iteration we can move to a reduced representative (the explicit formulae are a’=(f-b²)/a, b’=-b mod a’).

Maple procedures to do all this will be provided in the next post.

Reference
¹Computing in the Jacobian of a Hyperelliptic Curve D.Gantor Mathematics of Comptuation Vol.48.No.177 (Jan., 1987).

One of the most celebrated properties of elliptic curves is that the set of rational points is a group, with a highly geometric explanation of the group law: the ‘chord and tangent’ process. Two points and their sum are linked by consideration of the intersection of straight lines with the curve: as the curve is a cubic, there are three intersections (subject to some technical book-keeping with repeated points and the point ‘at infinity’). Such an approach clearly won’t transfer immediately to curves given by higher degree polynomials, as there will be more intersections, but as there are only finitely many, one would still hope to be able to define relationships between points. For instance, on an elliptic curve, if A, B and ∞ are colinear then B is -A; thus if on a more complicated curve we had A,B,C,∞ colinear it might make sense to think of C as -(A+B), and then A+C as -B and so on. That is to say, there may be relationships between groups of points rather than individual points.

In algebraic geometry, this (and much more) is captured by the notion of a divisor; rather than present them here in full generality, I will consider the specific case of divisors on (hyperelliptic) curves. These will then serve as the building blocks for a group structure connected to the curve which reduces in the special case of an elliptic curve to the familiar group of rational points.

To fix ideas, let K be a field of characteristic other than 2 with algebraic closure A. A curve C is described as a hyperelliptic curve of genus g if there is some degree 2g+1 polynomial f with distinct roots such that v²=f(u) is a model of C: so the familiar elliptic curves are the special cases with genus 1.

A point P on C is a pair (x,y) of elements of A (not K) satisfying y=f(x); or the point at infinity ∞. Then a divisor D of C is a finite formal sum Σ_im_iP_i for integers m_i and points P_i on C. D is described as having degree Σ_im_i; if all the m_i≥0 then we write D≥0. Formal (that is, pointwise) addition of divisors gives the additive group D of divisors; its identity is the divisor consisting of summing no points and it has a subgroup D₀ consisting of divisors with degree zero.

Any polynomial p(u,v) can be considered as a function on C of the form p=a(u)+b(u)v, since v²=f(u). If p vanishes at (x,y) then the order of the zero (x,y) of p is the exponent of the highest power of (u-x) which divides a²-b²f.

Thus we can define functions on C as h=p/q for p,q polynomials from K[u,v] such that v²-f(u) does not divide q(u,v): that is, q is not everywhere zero on C. Then h will have a finite set of zeros (those of p) and of poles (those of q); we associate to h a divisor, (h) = Σ_im_iP_i where the P_i are those zeros and poles and m_i their multiplicities:

If there is a nonzero function h on C such that D a divisor is (h), then D is described as principal. the principal divisors form a subgroup P of D₀ and hence D: the jacobian J of C is then the quotient D₀/P. That is, two divisors correspond to the same element of the jacobian if they differ by a principal divisor. This gives some idea as to how to simplify arbitrary divisors- we work in the jacobian and seek a simplest representative; that is, one comprised of the minimal number of points.

Consider that if (x,y) is a point P of C, then so is P’=(x,-y). The function u-x has zeros P and P’ with a double pole at ∞ so P+P’+∞ = (u-x) is principal and hence equivalent to zero mod P. Hence -P’ is equivalent to P-2∞ so we can rewrite divisors to only feature positive multiples of points other than ∞ Thus in J, where the degree is necessarily 0, any element has a representation

such that if P_i appears in D, then no P_j=P’ for any j different to i. Hence, any point of the form (x,0) will appear at most once. Such a representation is called semi-reduced; if r≤g then it is called reduced.

Remarkably, (by the Riemann-Roch theorem) any divisor in the Jacobian will have a unique, reduced representative (in other words, any divisor is the sum of a reduced divisor and a principal divisor). Now we can see what’s really going on with the elliptic curve group law: as a reduced divisor will have r≤1, it takes the form P-&infty; so there is an obvious isomorphism between the set of rational points and the Jacobian. Hence adding two points A,B on the curve gives rise to another point of the curve, by reducing the divisor A+B-2∞ to some representative C-∞ and setting A+B=C.

But with hyperelliptic curves, this needn’t be the case: the sum of two points is a perfectly good reduced divisor in the next simplest case of genus 2, for instance, so we can’t add two points and expect the answer to be a point. Hence we need to consider the divisors corresponding to rational points in the broader setting of the jacobian; to extract useful information about those points, we’ll need to consider the rational divisors. This motivates an alternative notation for divisors, more suitable to computation: I leave all these issues to the next post.

The sixth edition of the Carnival of Mathematics will be hosted here in about a fortnight. To submit articles, email me via carnival [at] straylight.co.uk.

Due to travel commitments I shall be unplugged on the Friday itself, so I intend to post on Thursday, April 19th (modulo timezones; I’m on British Summer Time). So please let me have your articles by then!

For now, enjoy today’s carnival from Science and Reason.

ella is an update of gla, the elliptic curve group law procedures, to work with the generic_group procedures described previously.

An arbitrary point P is now either a list [x,y] or the identity element zero. Addition of two such points P,Q is given by ellGroupLaw(P,Q) whilst ellMinus(P) gives the inverse. So these functions can be used as arguments for ncopies and so on. Setting up the curve is as described for gla: specify variables a_1 through a_6 and optionally set workModM and a modulus M for computation over prime fields. The getQuantities function is also included for convenience; order calculations and functions like the old mnadd should make use of the generic_group procedures and thus are omitted.

I’m keeping gla available for use with torsion_tools, most of the functions of the latter depend strongly on the underlying group being that of an elliptic curve so cannot be translated to generic form, so I can’t be bothered to update the notation from x,y to [x,y] !

Overview

For the last month or so I’ve been working with hyperelliptic rather than elliptic curves. This requires working in the Jacobian of the curve rather than the curve itself, but the basic computational tasks are of course the same: adding arbitrary points, multiplication by m, finding orders. I wrote Maple code for all of these in the elliptic curve case, but the simplicity of both the group law and the examples I worked on meant I could get away with brute force computation of these. But for higher genus (even genus 2), this becomes crippling very early on, so I needed some smarter methods. Having discovered that you can pass functions as arguments in Maple, it seemed best to divorce the group methods from the specifics of the group being computed with. To that end, I present generic_group, a set of Maple procedures for generic group algorithms.

A generic algorithm is one which only performs the group operation, inversion, or testing for equality. To that end, these procedures may take as arguments: elements; a function grouplaw that performs the group operation on an input of two elements; or another function groupminus that inverts its input element. Since I’m usually working with additive groups, the neutral element is given as zero, and so the supplied functions must be able to handle this.

The idea is that other sets of procedures will specify those functions: for instance, I’ve been writing procedures for the group of divisors of an algebraic curve: as a special case I have a function g2JacGroupLaw which will sum two rational divisors from the Jacobian of a genus 2 hyperelliptic curve. Rather than writing a multiplication by m function for such divisors, I just plug that function into the generic procedure for finding n copies of an element. I’ve updated my earlier elliptic curve procedures to this format as well.

The Procedures

Multiplication by n (ncopies and brutencopies)

A call of ncopies(n,g,grouplaw,groupminus) computes [n]g; it catches the special cases of n=0 (giving zero), n=1 (giving g) and n negative (giving [|n|](-g)).
This procedure uses around 2ceil(log₂n) instances of the group law by exploiting fast exponentiation, rather than naively adding successive terms. If out of boredom or to compare performance you want naive addition, you can use brutencopies(n,G,grouplaw,groupminus) instead.

Discrete Logarithm Problem (BSGSDL)

In the previous post I described the Baby Step, Giant Step algorithm for computing discrete logarithms, in the case of unknown order of the generator (Terr’s variant). BSGSDL(g,h,grouplaw) will use this to return an integer t such that [t]g=h; this assumes that there is such a t, i.e., that h is in <g>. beware that if it isn’t, the procedure will wander off to deep space and never terminate.

Order finding (BSGSOrder and bruteOrder)

Terr’s variant can be used to establish the order of an element by solving the DLP with h=zero; however you have to check that g itself is not the identity first. So BSGSOrder(g,grouplaw) will find the least t such that [t]g=zero. If you want to try this by checking successive multiples of g, you can use bruteOrder(g,grouplaw) instead; again, knowing nothing about the group neither of these procedures knows when to give up so can churn forever if g is of infinite order.

The discrete logarithm problem is the vital part of elliptic curve cryptography, but can be defined (to varying cryptographic strength) for any cyclic group:

Discrete Logarithm Problem (DLP)
Let G be a cyclic group, with operation ⊕. Let [n] represent (n-1)-fold application of ⊕ i.e., [2]g=g⊕g, [3]g=g⊕g⊕g etc.

Given g,h from G, the discrete logarithm problem is to find t such that [t]g=h.

The baby-step, giant step (BSGS) algorithm is a generic algorithm for solving the DLP- that is to say, it makes no appeal to properties of the group involved, merely calculating abstractly with ⊕. There is a theoretical upper bound to the effectiveness of generic algorithms, and BSGS approaches are of that order of magnitude.

The simplest demonstration of BSGS (the original by Shanks) assumes that g generates G, with both of known order n: recall that the group order is simply the number of elements it contains, whereas the order of an element g is the least n such that [n]g=id_G, should such a value exist. The order n of an element always divides the order of the group N, with equality when g generates G. Between the two there is also the exponent, the least value e such that [e]g=id_G for all g in G; for cyclic groups this is N, but for products of cyclic groups (the structure of groups of rational points) it is the lowest common multiple of their respective orders, and thus, although a divisor of N, may be significantly smaller than it.

So, if we can find an order m rational point on a curve, we know that the cardinality of the group of rational points is zero modulo m. By testing random points and taking the lowest common multiple of their order we can usually find the exponent e of the group. With luck, but not always, this will be large enough that when combined with bounds on the cardinality the latter is established exactly (as with modular information in the SEA algorithm).

But it is no good attempting to do so using an algorithm that requires the order of the point! There are BSGS algorithms for the DLP which can handle unknown order, for a given g we can apply these to solve for h=id_G in the cyclic group generated by g. Provided the algorithm gives the minimal t such that [t]g=h=id_G in G=<g>, then t is the order of g.

One such algorithm, by Terr, is given in Cohen and Frey’s Handbook of Elliptic and Hyperelliptic curve cryptography (my current bible!) It relies on the following observation:

Let T_n be the nth triangular number: that is, defined by the recursion T₁=0, T_n+1=T_n+n.

Then any non-negative integer t, there are unique integers j and k with t=T_j+1-k with 0≤k<j.

To see how, notice that there is a unique j such that t lies in the interval (T_j , … , T_j+1]=(T_j+1-j , … , T_j+1-0] and that this interval has width j so there is an appropriate choice of k.

We then suppose that t satisfies [t]g=h. Then we have [T_j+1]g=h⊕[k]g. So, instead of testing each [t] in turn until we hit equality, for a given j we need only test the ‘giant step’ [T_j+1]g against the set of ‘baby steps’ β={β_i}={h⊕[0]g,…,h⊕[i]g,…,h⊕[j-1]g. If that j yields no matches, we move to j’=j+1: by keeping track of [j]g at each iteration, the new T_j’+1 and the extra h⊕[j’-1]g are found by a single group operation each. Hence this is attractive from both storage and time complexity perspectives: we need only record the baby steps β, [j]g and a single giant step at any given iteration j, whilst the time complexity is of order t^1/2.

Terr’s BSGS variant for the DLP
Finds t such that [t]g=h for g generating G of unknown order, h from G.

Initialise β={β₀=h}, γ=δ=id_G, j=0. ((For each iteration, we have γ=[T_j+1]g and δ=[j]g)
Then loop over j as follows:

• Increment j by 1, then update:
• Set δ=δ⊕g=[j-1]g⊕g=[j]g.
• Set γ=γ⊕δ=[T_j]g+[j]g=[T_j+1]g.
• If j≥2 then
  • For s from 0 to j, if γ=β_s then return T_j+1-s
• Add β_j=β_j-1⊕g to β

I’ve implemented this generic DLP algorithm and an order-finding version (which requires you to catch g=id_G) as Maple procedures for arbitrary groups- details on that will be in the next post! BSGS-based approaches become impractical at finite field sizes well within the grasp of SEA for counting on elliptic curves; but are of interest in the higher genus case which lacks an Elkies procedure.