Worst-case complexity bounds for algorithms in the theory of integral quadratic forms

DOI10.1016/0196-6774(80)90021-8zbMath0473.68030MaRDI QIDQ3928238

Jeffrey C. Lagarias

Publication date: 1980

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(80)90021-8

zbMATH Keywords

binary quadratic Diophantine equations; polynomial worst-case running time bounds

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11D09: Quadratic and bilinear Diophantine equations

11A63: Radix representation; digital problems

Related Items

Density computations for real quadratic units, Smallest Reduction Matrix of Binary Quadratic Forms, Selected Applications of LLL in Number Theory, On the computation of quadratic 2-class groups, Algorithms to construct Minkowski reduced and Hermite reduced lattice bases, A hierarchy of polynomial time lattice basis reduction algorithms, A key-exchange system based on imaginary quadratic fields, Iterated ring class fields and the icosahedron, An algorithm for finding a shortest vector in a two-dimensional modular lattice, The optimal LLL algorithm is still polynomial in fixed dimension., Short vectors of planar lattices via continued fractions, A linear algorithm for integer programming in the plane, On the parametrization of solutions of quadratic equations, Identification and signatures based on NP-hard problems of indefinite quadratic forms, A Rigorous Time Bound for Factoring Integers