Type: Seminar

Distribution: World

Expiry: 10 Sep 2009

Auth: billu@daumier.maths.usyd.edu.au

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.