Computational Algebra Seminar: Bauch -- Fast Arithmetic in the Divisor Class Group

Speaker: Jens Bauch
Title: Fast Arithmetic in the Divisor Class Group
Time & Place: Carslaw 535, 2-3pm, Thursday 8 March

Abstract:
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.