An Analysis of the Reduction Algorithms for Binary Quadratic Forms

Ingrid Biehl

1997 · 11 citations · 0 references

Concepts

Abstract

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 ...