Fast quantum algorithms for computing the unit group and class group of a number field

Research output: Contribution to journalConference articlepeer-review

50 Scopus citations

Abstract

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 solving Pell's equation, which is 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.

Original languageEnglish (US)
Pages (from-to)468-474
Number of pages7
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2005
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Fast quantum algorithms for computing the unit group and class group of a number field'. Together they form a unique fingerprint.

Cite this