We present an algorithm for computing the class number of the quadratic number field of discriminant d. The algorithm terminates unconditionally with the correct answer and, under the GRH, executes in O-epsilon(vertical bar d vertical bar(1/4+epsilon)) steps. The technique used combines algebraic methods with Burgess' theorem on character sums to estimate L( 1, chi(d)). We give an explicit version of Burgess' theorem valid for prime discriminants and, as an application, we compute the class number of a 32-digit discriminant.
|Translated title of the contribution||Quadratic class numbers and character sums|
|Pages (from-to)||1481 - 1492|
|Number of pages||12|
|Journal||Mathematics of Computation|
|Publication status||Published - Jul 2006|
Bibliographical notePublisher: American Mathematical Society
Other identifier: IDS number 065TF