Mathematics of Computation · 1989 · 23 citations · 10 references
Natural SciencesComputer ScienceMathematicsAlgebraAlgorithmsNumber TheoryAbstract AlgebraAlgebraic Number TheoryAnalytic Number TheoryArithmetic GeometryComputational Number TheoryNumber-theoretic AlgorithmsAlgebraic Number ComputationAlgebraic Number Field ComputationsClass Number ComputationClass Number FormulasComputing Zeta FunctionsRiemann Zeta Function
It is shown how the analytic class number formula can be used to produce an algorithm which efficiently computes the class number <italic>h</italic> of an algebraic number field <italic>F</italic>. The method assumes the truth of the Generalized Riemann Hypothesis in order to estimate the residue of the Dedekind zeta function of <italic>F</italic> at <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s equals 1"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">s = 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sufficiently well that <italic>h</italic> can be determined unambiguously. Given the regulator <italic>R</italic> of <italic>F</italic> and a known divisor <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h Superscript asterisk"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{h^ \ast }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <italic>h</italic>, it is shown that this technique will produce the value of <italic>h</italic> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartAbsoluteValue d Subscript upper F Baseline EndAbsoluteValue Superscript 1 plus epsilon Baseline slash left-parenthesis h Superscript asterisk Baseline upper R right-parenthesis squared right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:mrow> <mml:mi>R</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(|{d_F}{|^{1 + \varepsilon }}/{({h^ \ast }R)^2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> elementary operations, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d Subscript upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{d_F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the discriminant of <italic>F</italic>. Thus, if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h greater-than StartAbsoluteValue d Subscript upper F Baseline EndAbsoluteValue Superscript 1 slash 8"> <mml:semantics> <mml:mrow> <mml:mi>h</mml:mi> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>8</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">h > |{d_F}{|^{1/8}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, then the complexity of computing <italic>h</italic> (with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h Superscript asterisk Baseline equals 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>h</mml:mi> <mml:mo>∗</mml:mo> </mml:msup> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">{h^ \ast } = 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>) is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis StartAbsoluteValue d Subscript upper F Baseline EndAbsoluteValue Superscript 1 slash 4 plus epsilon Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>d</mml:mi> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(|{d_F}{|^{1/4 + \varepsilon }})</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
10
The Art of Computer Programming, Vol. 2
Donald E. Knuth · Medical Entomology and Zoology · 1981 · 863 citations