Paper Info
Title
On the Complexity of Computing Units in a Number Field
Abstract
Given an algebraic number field K, such that [K : Q] is constant, we show that the problem of computing the units group O-K is in the complexity class SPP. As a consequence, we show that principal ideal testing for an ideal in O-K is in SPP. Furthermore, assuming the GRH, the class number of K, and a presentation for the class group of K can also be computed in SPP. A corollary of our result is that solving PELL'S EQUATION, recently shown by Hallgren [121 to have a quantum polynomial-time algorithm, is also in SPP.
Year
DOI
Venue
2004
10.1007/978-3-540-24847-7_5
ALGORITHMIC NUMBER THEORY, PROCEEDINGS
Keywords
Field
DocType
polynomial time
Complexity class,Discrete mathematics,Quantum,Combinatorics,Algebraic number,Class number,Algebraic number field,Time complexity,Principal ideal,Mathematics,Computational complexity theory
Conference
Volume
ISSN
Citations 
3076
0302-9743
2
PageRank 
References 
Authors
0.42
9
2
Name
Order
Citations
PageRank
Vikraman Arvind129638.18
Piyush P. Kurur2889.41