Computational Algebra Seminar: Khuri-Makdisi -- Fast arithmetic in Picard groups of general curves

Speaker:  Kamal Khuri-Makdisi (American University of Beirut)
Title: Fast arithmetic in Picard groups of general curves
Time & Place: 3-4pm, Thursday 10 September, Carslaw 535

Abstract:
Let C be a projective smooth curve of genus g over a field k.
The Picard group of C over k, consisting of k-rational divisors up to
linear equivalence, is analogous to the ideal class group of a number
field.  In this talk, I will describe "geometric" algorithms for the group
arithmetic in Pic^0 that boil down to linear algebra in vector spaces of
dimension O(g log g).  Using fast linear algebra, this yields a complexity
of O(g^2.376) field operations in k per group operation in the Picard
group.  In comparison, existing "arithmetic" algorithms based on the
analogy with ideal class groups have a complexity of O(g^4) for general
curves of genus g, but attain O(g^2) if one restricts to special classes of
curves.