1997 · 11 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsNumber TheoryTheory Of ComputationNumber-theoretic AlgorithmsQuadratic FormsIntegral Quadratic FormsPositive Definite Quadratic FormsQuadratic FieldsReduced Quadratic Forms
We prove in this paper that the classical reduction algorithms for integral binary quadratic forms have quadratic running time. 1 Introduction The reduction algorithm for binary quadratic forms, invented by Lagrange, Legendre, and Gauß is one of the most fundamental and important algorithms in the algorithmic theory of binary quadratic forms and quadratic fields. It permits to find the successive minima of positive definite binary quadratic forms, to decide the equivalence of integral binary quadratic forms, to compute the fundamental unit of real quadratic orders, to compute in the class group of quadratic fields etc. The efficiency of the methods for solving the above problems depends heavily on the efficiency of reduction. In [Lag80] Lagarias slightly modified the classical reduction algorithm and proved that his modification reduces a form f in time O(nM(n)) where n is the length of the bit string necessary to represent f (see below for a more precise definition) and M(n) is the ...