Conference abstracts

Session A3 - Computational Number Theory

July 10, 17:40 ~ 18:20

Fast Arithmetic in the Divisor Class Group

Jens Bauch

Simon Fraser University, Canada   -   jd.bauch@gmail.com

Let $C$ be a smooth projective geometrically irreducible algebraic curve of genus $g$ over a field $k$. The Jacobian variety $J$ of $C$ is a $g$-dimensional algebraic group that parametrizes the degree zero divisors on $C$, up to linear equivalence. Khuri-Makdisi showed that the basic arithmetic in $J$ can be realized in an asymptotic complexity of $O(g^{3+\epsilon})$ field operations in $k$. Denote by $F=k(C)$ the function field of the curve. Then the elements of $J$ can be identified with divisor classes $[D]$ of the function field $F/k$ where $D$ can be represented by a lattice $L_D$ over the polynomial ring $k[t]$. In fact, the class $[D]$ can be parametrized in terms of invariants of the lattice $L_D$. The basic arithmetic (addition and inversion) in $J$ can then be realized asymptotically in $O(g^3)$ field operations in $k$ and beats the one of Khuri-Makdisi. Under reasonable assumptions the runtime can be reduced to $O(g^2)$ field operations.

View abstract PDF



FoCM 2017, based on a nodethirtythree design.