Divisor Class Group Arithmetic on C3,4 Curves
Date
2020-01-31
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Computing in the divisor class group of an algebraic curve is a non-trivial component in computing L-series. L-series in turn are at the heart of the Sato-Tate conjecture and related conjectures. The Sato-Tate conjecture has been proven for elliptic curves with complex multiplication, but remains open for other families of algebraic curves. In order to test these conjectures against other curve families, it is desirable to have efficient algorithms to perform divisor class group arithmetic. Fast explicit formulas exist to perform divisor class group arithmetic for genus 1 and genus 2 curves. However, the picture for genus 3 curves is incomplete. Existing explicit formulas for arithmetic on non-hyperelliptic genus 3 curves (C3,4 curves) have been developed with cryptographic applications in mind. They make certain genericity assumptions on their inputs that hold with high probability in cryptographic settings, but are unsuited for number theoretic use cases. More general algorithms exist that can perform divisor class arithmetic over any curve, but they are slow. In this thesis, that gap is bridged. Fast explicit formulae are developed that may be used to add any pair of reduced divisors on any C3,4 curve. Formulae optimized for the generic case considered by previous authors are produced, allowing one to add divisors in 1I+111M+3S+99A and double divisors in 1I+135M+3S+116A (inversions, multiplications, squarings, and additions in a field). The formulae are implemented in Sage. Benchmark tests find that these new formulae allow one to add and double 13.2% and 11.1% faster, respectively, that the previous state-of-the-art in C3,4 curve arithmetic.
Description
Keywords
Algebraic Geometry, Computational Algebraic Geometry, Plane Curves, Divisor Class Group, Jacobian, Global Fields
Citation
MacNeil, E. (2020). Divisor Class Group Arithmetic on C3,4 Curves (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.