Paper Info
Title
Worst-case complexity bounds for algorithms in the theory of integral quadratic forms
Abstract
The problem of factoring an integer and many other number-theoretic problems can be formulated in terms of binary quadratic Diophantine equations. This class of equations is also significant in complexity theory, subclasses of it having provided most of the natural examples of problems apparently intermediate in difficulty between P and NP-complete problems, as well as NP-complete problems [2, 3, 22, 26]. The theory of integral quadratic forms developed by Gauss gives some of the deepest known insights into the structure of classes of binary quadratic Diophantine equations. This paper establishes explicit polynomial worst-case running time bounds for algorithms to solve certain of the problems in this theory. These include algorithms to do the following: (1) reduce a given integral binary quadratic form; (2) quasi-reduce a given integral ternary quadratic form; (3) produce a form composed of two given integral binary quadratic forms; (4) calculate genus characters of a given integral binary quadratic form, when a complete prime factorization of its determinant D is given as input; (5) produce a form that is the square root under composition of a given form (when it exists), when a complete factorization of D and a quadratic nonresidue for each prime dividing D is given as input.
Year
DOI
Venue
1980
10.1016/0196-6774(80)90021-8
Journal of Algorithms
Keywords
Field
DocType
quadratic form
Isotropic quadratic form,Discrete mathematics,Binary quadratic form,Quadratic residue,Combinatorics,Quadratic form,Algorithm,Quadratic function,Definite quadratic form,Quadratic field,Mathematics,Solving quadratic equations with continued fractions
Journal
Volume
Issue
ISSN
1
2
0196-6774
Citations 
PageRank 
References 
30
14.50
6
Authors
1
Name
Order
Citations
PageRank
J. C. Lagarias1563235.61