Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
From MaRDI portal
Publication:3220657
DOI10.2307/2007966zbMath0556.10022OpenAlexW4237103727MaRDI QIDQ3220657
Ulrich Fincke, Michael E. Pohst
Publication date: 1985
Full work available at URL: https://doi.org/10.2307/2007966
algorithmnumerical examplesellipsoidcomplexity analysisreduction theoryCholesky's methodlattices of higher dimensionsvectors of short length
Analysis of algorithms and problem complexity (68Q25) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Minima of forms (11H50)
Related Items (only showing first 100 items - show all)
Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method ⋮ Individual discrete logarithm with sublattice reduction ⋮ Solving 𝑆-unit, Mordell, Thue, Thue–Mahler and Generalized Ramanujan–Nagell Equations via the Shimura–Taniyama Conjecture ⋮ The size function for imaginary cyclic sextic fields ⋮ Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation ⋮ Numerical computation of endomorphism rings of Jacobians ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation ⋮ A parallel search for good lattice points using LLL-spectral tests ⋮ Determining the small solutions to 𝑆-unit equations ⋮ Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Efficient lattice assessment for LCG and GLP parameter searches ⋮ Space-time coding and signal processing for MIMO communications ⋮ Sieve, Enumerate, Slice, and Lift: ⋮ Computing points of bounded height in projective space over a number field ⋮ On principal ideal testing in algebraic number fields ⋮ Factorization properties of lattices over the integers ⋮ Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing ⋮ A survey of VLSI implementations of tree search algorithms for MIMO detection ⋮ Unnamed Item ⋮ 32-bit multipliers for linear congruential random number generators ⋮ Binary Hermitian Lattices over Number Fields ⋮ On the practical solution of the Thue equation ⋮ Unnamed Item ⋮ A revised forward and backward heuristic for two-term multiple recursive random number generators ⋮ Lattice basis reduction for indefinite forms and an application ⋮ An analysis of linear congruential random number generators when multiplier restrictions exist ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Improvements in closest point search based on dual HKZ-bases ⋮ Lattice Point Enumeration on Block Reduced Bases ⋮ Finding shortest lattice vectors faster using quantum search ⋮ Finding a shortest vector in a two-dimensional lattice modulo m ⋮ Discrete series multiplicities for classical groups over \(\mathbb{Z}\) and level 1 algebraic cusp forms ⋮ Lattice Sieving via Quantum Random Walks ⋮ Constructive spherical codes near the Shannon bound ⋮ On the number of lattice points in a small sphere and a recursive lattice decoding algorithm ⋮ Improved computation of fundamental domains for arithmetic Fuchsian groups ⋮ Ellipsoid Bounds for Convex Quadratic Integer Programming ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Sieving for closest lattice vectors (with preprocessing) ⋮ Computing dimensions of spaces of Arakelov divisors of number fields ⋮ MLAMBDA: a modified LAMBDA method for integer least-squares estimation ⋮ The characteristic masses of Niemeier lattices ⋮ Implementation aspects of list sphere decoder algorithms for MIMO-OFDM systems ⋮ Orbits and lattices for linear random number generators with composite moduli ⋮ Sieve algorithms for the shortest vector problem are practical ⋮ Comment on: ``Sum of squares of uniform random variables by I. Weissman ⋮ Spectral Analysis of the MIXMAX Random Number Generators ⋮ A new heuristic for second-order multiple recursive random number generator ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Voronoi polytopes for polyhedral norms on lattices ⋮ An improved LLL algorithm ⋮ A backward heuristic algorithm for two-term multiple recursive random number generators ⋮ The hypermetric cone and polytope on eight vertices and some generalizations ⋮ A semidefinite programming method for integer convex quadratic minimization ⋮ The Computation of Sextic Fields with a Cubic Subfield and no Quadratic Subfield ⋮ FPT-algorithms for some problems related to integer programming ⋮ Computing power integral bases in quartic relative extensions ⋮ On the resolution of relative Thue equations ⋮ Completed \({\mathcal {GPS}}\) covers all bent functions ⋮ Random Sampling Revisited: Lattice Enumeration with Discrete Pruning ⋮ Computing All Elliptic Curves Over an Arbitrary Number Field with Prescribed Primes of Bad Reduction ⋮ The size function for quadratic extensions of complex quadratic fields ⋮ A new effective branch-and-bound algorithm to the high order MIMO detection problem ⋮ An exhaustive analysis of two-term multiple recursive random number generators with efficient multipliers ⋮ Topics in computational algebraic number theory ⋮ A simplex algorithm for rational cp-factorization ⋮ Hermite’s Constant and Lattice Algorithms ⋮ Selected Applications of LLL in Number Theory ⋮ An effective branch-and-bound algorithm for convex quadratic integer programming ⋮ Koblitz curve cryptosystems ⋮ Optimal systems of fundamental \(S\)-units for LLL-reduction ⋮ New sums of three cubes ⋮ On the Iwasawa $\lambda $-invariant of the cyclotomic $\mathbb {Z}_2$-extension of $\mathbb {Q}(\sqrt {p} )$ ⋮ Solving exponential diophantine equations using lattice basis reduction algorithms ⋮ CM liftings of supersingular elliptic curves ⋮ Extensions on ellipsoid bounds for quadratic integer programming ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Computing integral points on \(X_{\mathrm{ns}}^+(p)\) ⋮ Some properties of \(\tau\)-adic expansions on hyperelliptic Koblitz curves ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem ⋮ On the Computation of Unit Groups and Class Groups of Totally Real Quartic Fields ⋮ Improvements in the analysis of Kannan's CVP algorithm ⋮ The shortest vector problem and tame kernels of cyclotomic fields ⋮ High-rate space-time block codes from twisted Laurent series rings ⋮ Full period and spectral test of linear congruential generator and second-order multiple recursive generator ⋮ A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge ⋮ The weighted sum of two S-units being a square ⋮ The randomized slicer for CVPP: sharper, faster, smaller, batchier ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Advanced lattice sieving on GPUs, with tensor cores ⋮ Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes ⋮ On the computation of units and class numbers by a generalization of Lagrange's algorithm ⋮ Unnamed Item ⋮ Computing fundamental domains for Fuchsian groups ⋮ On the solution of units and index form equations in algebraic number fields ⋮ Searching for good two-term multiple recursive random number generators using a backpropagation algorithm ⋮ Reduced complexity \(K\) -best sphere decoder design for MIMO systems
This page was built for publication: Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
