The Behavior of Random Reduced Bases

DOI10.1093/IMRN/RNX074zbMATH Open1452.11148arXiv1608.00767OpenAlexW2964337207MaRDI QIDQ4619465FDOQ4619465

Authors: Seungki Kim, Akshay Venkatesh 

Publication date: 6 February 2019

Published in: IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Abstract: We prove that the number of Siegel-reduced bases for a randomly chosen $n$-dimensional lattice becomes, for $nightarrowinfty$, tightly concentrated around its mean. We also show that most reduced bases behave as in the worst-case analysis of lattice reduction. Comparing with experiment, these results suggest that most reduced bases will, in fact, "very rarely" occur as an output of lattice reduction. The concentration result is based on an analysis of the spectral theory of Eisenstein series and uses (probably in a removable way) the Riemann hypothesis.

Full work available at URL: https://arxiv.org/abs/1608.00767

Recommendations

• On the reduction of a random basis
• On the reduction of a random basis
• Reducibilities relating to Schnorr randomness
• scientific article; zbMATH DE number 952958
• Reducts of the random partial order
• Approximation with random bases: pro et contra
• On Nearly Orthogonal Lattice Bases and Random Lattices
• scientific article; zbMATH DE number 1557032
• Reduction of lattice bases for arbitrary norms
• Random bases for coprime linear groups

zbMATH Keywords

Eisenstein seriesLLL-algorithmSiegel-reduced basis

Mathematics Subject Classification ID

Siegel modular groups; Siegel and Hilbert-Siegel modular and automorphic forms (11F46) Number-theoretic algorithms; complexity (11Y16)

Cited In (11)

• Random affine lattices
• Volumes and distributions for random unimodular complex and quaternion lattices
• Algorithmic Number Theory
• A physical study of the LLL algorithm
• Improved Herrmann-May's attack with merging variables and lower LLL bound
• Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
• On the reduction of a random basis
• On the reduction of a random basis
• On Nearly Orthogonal Lattice Bases and Random Lattices
• Mean value formulas on sublattices and flags of the random lattice
• The Beauty and the Beasts -- the hard cases in LLL reduction

This page was built for publication: The Behavior of Random Reduced Bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4619465)