An LLL Algorithm with Quadratic Complexity
From MaRDI portal
Publication:3575152
DOI10.1137/070705702zbMath1214.11139OpenAlexW2072079288WikidataQ64356158 ScholiaQ64356158MaRDI QIDQ3575152
Damien Stehlé, Phong Q. Nguyen
Publication date: 7 July 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/74867a8cca634051b8d90955ea22f57c479c18a6
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)
Related Items
Towards faster polynomial-time lattice reduction ⋮ Perturbation Analysis of the QR factor R in the context of LLL lattice basis reduction ⋮ Computing points of bounded height in projective space over a number field ⋮ Recovering Exact Results from Inexact Numerical Data in Algebraic Geometry ⋮ An efficient lattice reduction using reuse technique blockwisely on NTRU ⋮ Algebraic number fields and the LLL algorithm ⋮ Greedy algorithm computing Minkowski reduced lattice bases with quadratic bit complexity of input vectors ⋮ Deterministic factoring with oracles ⋮ On the modular inversion hidden number problem ⋮ Improving bounds on elliptic curve hidden number problem for ECDH key exchange ⋮ Fast practical lattice reduction through iterated compression ⋮ Methodologies of Symbolic Computation ⋮ Gradual sub-lattice reduction and a new complexity for factoring polynomials ⋮ On the computation of the HNF of a module over the ring of integers of a number field ⋮ Cryptanalysis of a Homomorphic Encryption Scheme Over Integers ⋮ Linear forms in logarithms and the mathematical method of Diophantine equations: applications in chemistry and physics ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction ⋮ List decoding of number field codes ⋮ Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA ⋮ Common modulus attacks on small private exponent RSA and some fast variants (in practice) ⋮ Small CRT-exponent RSA revisited ⋮ An experimental comparison of some LLL-type lattice basis reduction algorithms ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem ⋮ Cryptanalysis of elliptic curve hidden number problem from PKC 2017 ⋮ Linear programming using limited-precision oracles ⋮ Refined analysis to the extended tower number field sieve ⋮ Generalized cryptanalysis of small CRT-exponent RSA ⋮ A polynomial-time algorithm for solving the hidden subset sum problem ⋮ A practical algorithm for completing half-Hadamard matrices using LLL ⋮ Approximating the densest sublattice from Rankin’s inequality ⋮ Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\) ⋮ On the quantum complexity of the continuous hidden subgroup problem
