A quantum algorithm for computing the unit group of a number field and connections to post-quantum cryptographyAlgebra & Discrete Mathematics
|Kirsten Eisenträger, Penn State U
|Thu, Nov 5 2020, 10:00AM
Computing the group of units in a number field is one of the central tasks of computational algebraic number theory. It is believed to be hard classically, which is of interest for cryptography. In the quantum setting, efficient algorithms were previously only known for number fields of constant degree. We will give a quantum algorithm that is polynomial in the degree of the field and the logarithm of its discriminant and discuss connections to post-quantum cryptography.
Joint work with Sean Hallgren, Alexei Kitaev, and Fang Song.
Stay afterwards for a brief, informal reception. Refreshments will be self-provided.