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 language | English (US) |
|---|---|
| Pages (from-to) | 468-474 |
| Number of pages | 7 |
| Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
| DOIs | |
| State | Published - 2005 |
| Event | 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005 |
All Science Journal Classification (ASJC) codes
- Software