Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field

DCM/DS Seminar
Topic:Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field
Speaker:Sean Hallgren
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.