An LLL algorithm with quadratic complexity
From MaRDI portal
Publication:3575152
DOI10.1137/070705702zbMATH Open1214.11139OpenAlexW2072079288WikidataQ64356158 ScholiaQ64356158MaRDI QIDQ3575152FDOQ3575152
Authors: Phong Q. Nguyen, Damien Stehlé 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Lattices and convex bodies (number-theoretic aspects) (11H06) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Number-theoretic algorithms; complexity (11Y16)
Cited In (61)
- Improved computation of polynomial roots over number fields when using complex embeddings
- Formalizing the LLL basis reduction algorithm and the LLL factorization algorithm in Isabelle/HOL
- A pivoted LLL algorithm
- Generalized cryptanalysis of small CRT-exponent RSA
- Algorithmic Number Theory
- Computing points of bounded height in projective space over a number field
- The optimal LLL algorithm is still polynomial in fixed dimension.
- Fast practical lattice reduction through iterated compression
- On the modular inversion hidden number problem
- Title not available (Why is that?)
- Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA
- Improved Herrmann-May's attack with merging variables and lower LLL bound
- Linear programming using limited-precision oracles
- A practical algorithm for completing half-Hadamard matrices using LLL
- Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
- On the quantum complexity of the continuous hidden subgroup problem
- Title not available (Why is that?)
- Linear forms in logarithms and the mathematical method of Diophantine equations: applications in chemistry and physics
- Approximating the densest sublattice from Rankin's inequality
- Adaptive precision floating point LLL
- Certified lattice reduction
- Small CRT-exponent RSA revisited
- Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
- Gradual sub-lattice reduction and a new complexity for factoring polynomials
- A parametric version of LLL and some consequences: parametric shortest and closest vector problems
- An experimental comparison of some LLL-type lattice basis reduction algorithms
- Algebraic number fields and the LLL algorithm
- H-LLL: using Householder inside LLL
- Searching worst cases of a one-variable function using lattice reduction
- An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
- Parallel Cholesky-based reduction for the weighted integer least squares problem
- List decoding of number field codes
- Progress on LLL and lattice reduction
- A formalization of the LLL basis reduction algorithm
- Title not available (Why is that?)
- Improving bounds on elliptic curve hidden number problem for ECDH key exchange
- Computing an LLL-reduced basis of the orthogonal latice
- An efficient lattice reduction using reuse technique blockwisely on NTRU
- A generalization of LLL lattice basis reduction over imaginary quadratic fields
- The history of the LLL-algorithm
- Analysis of the upper bound on the complexity of LLL algorithm
- Methodologies of Symbolic Computation
- Selected applications of LLL in number theory
- Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction
- Cryptanalysis of a homomorphic encryption scheme over integers
- Effect of the interval-symbol method with correct zero rewriting on the \(\delta\)-LLL algorithm
- Greedy algorithm computing Minkowski reduced lattice bases with quadratic bit complexity of input vectors
- LLL reduction and a conjecture of Gunnells
- Cryptanalysis of elliptic curve hidden number problem from PKC 2017
- Two-torsion subgroups of some modular Jacobians
- An improved LLL algorithm
- Refined analysis to the extended tower number field sieve
- Towards faster polynomial-time lattice reduction
- Solving the FCSR synthesis problem for multi-sequences by lattice basis reduction
- Common modulus attacks on small private exponent RSA and some fast variants (in practice)
- Recovering exact results from inexact numerical data in algebraic geometry
- On the computation of the HNF of a module over the ring of integers of a number field
- Deterministic factoring with oracles
- A polynomial-time algorithm for solving the hidden subset sum problem
- An LLL algorithm for module lattices
- A verified efficient implementation of the LLL basis reduction algorithm
This page was built for publication: An LLL algorithm with quadratic complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3575152)
