|Topic:||Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field|
|Affiliation:||NEC Research, Princeton|
|Date:||Monday, May 3|
|Time/Room:||11:15am - 12:15pm/S-101|
Computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. Factoring integers reduces to a special case of computing the unit group, but a reduction in the other direction is not known and appears more difficult. We give polynomial-time quantum algorithms for computing the unit group and class group when the number field has constant degree.