Eastern Great Lakes Theory Workshop Talk

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

Sean Hallgren, Pennsylvania State University

Saturday, September 10, 4:00-5:00pm

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 representatives can be computed efficiently.

Speaker Bio

Sean Hallgren is an Associate Professor at Penn State University. He works on quantum computation, with an emphasis on understanding when there are exponential speedups by quantum algorithms. He received his B.S. from Carnegie Mellon University and his Ph.D. from the University of California, Berkeley. Prior to joining Penn State he ran the quantum computing group at NEC Laboratories. He is a recipient of the NSF CAREER award, the PECASE award and two teaching awards.

< Schedule < EaGL-IV homepage