Genus 2 jacobian group law in Maple
April 18th, 2007Update 4/v/07: I’ve switched from Cantor’s definitions for a curve of the form y2=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 y2=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.