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

Dirichlet’s proof of the three-square theorem: An algorithmic perspective, 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, Bandwidth-efficient threshold EC-DSA, A tighter proof for CCA secure inner product functional encryption: genericity meets efficiency, InfoMod: a visual and computational approach to Gauss' binary quadratic forms, On the parametrization of solutions of quadratic equations, How to pick a random integer matrix? (and other questions), Identification and signatures based on NP-hard problems of indefinite quadratic forms, A Rigorous Time Bound for Factoring Integers