Tenth Algorithmic Number Theory Symposium ANTS-X University of California, San Diego July 9 – 13, 2012 Tenth Algorithmic Number Theory Symposium (ANTS-X) July 9 – 13, 2012

Computing the unit group, class group and compact representations in algebraic function fields

Kirsten Eisenträger and Sean Hallgren

Abstract: Number fields and global function fields have many similar properties. Both have many applications to cryptography and coding theory, and the main computational problems for number fields, such as computing the ring of integers and computing the class group and the unit group, have analogues over function fields. The complexity of the number field problems has been studied extensively and these problems have been the source of some exponential speedups by quantum computation. In this paper we study the analogous problems in function fields. We show that there are efficient quantum algorithms for computing the unit group, the class group and for solving the principal ideal problem in function fields of arbitrary degree. We show that compact representations exist, which allows us to show that the principal ideal problem is in NP. Unlike the number field case, we are also able to show that these compact representations can be computed efficiently.

Files available: paper (PDF)