Experimental Mathematics · 1999 · 26 citations · 5 references
ComputingComputer ScienceMathematicsAlgorithmsNumber TheoryTheory Of ComputationAlgebraic Number TheoryArithmetic GeometryComputational AlgebraNumber-theoretic AlgorithmsNumerical AlgorithmsArithmetic Of Finite FieldsPolynomial ExpansionQuadratic Fields
We develop methods for the rapid computation of the regulator of a real quadratic congruence function field K = k(x)(√D). By extending Shanks' infrastructure ideas in real quadratic number fields to real quadratic congruence function fields we obtain a baby step–giant step method for evaluating the regulator of K in O(|D|¼) polynomial operations. We also show the existence of an effective algorithm which computes the regulator unconditionally in O(|D|⅕) polynomial operations. By implementing both methods on a computer, we found that the O(|D|⅕) algorithm tends to be far better than the baby step–giant step algorithm in those cases where the regulator exceeds 108.
5