Modulo Errors

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.