Vol. 1, No. 1, 2013

Download this article
Download this article For screen
For printing
Recent Volumes
1: ANTS X
The Open Book Series
About the Series
Ethics Statement
Computing the unit group, class group, and compact representations in algebraic function fields

Kirsten Eisenträger and Sean Hallgren

Vol. 1 (2013), No. 1, 335–358
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 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
Mathematical Subject Classification 2010
Primary: 11Y16
Secondary: 11R27, 11R29
Milestones
Published: 14 November 2013
Authors
Kirsten Eisenträger
Department of Mathematics
Penn State University
University Park, PA 16802
United States
Sean Hallgren
Department of Computer Science and Engineering
Penn State University
University Park, PA 16802
United States