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 quantum computation
has provided exponential speedups for some of these problems. In this paper we
study the analogous problems in function fields. We show that there are efficient
quantum algorithms for computing the unit group, for computing 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. We are also able to show that these compact
representations can be computed efficiently, in contrast with the number field
case.
Keywords
function fields, compact representations, infrastructure,
unit group, principal ideal problem
