The Behavior of Random Reduced Bases

DOI10.1093/IMRN/RNX074MaRDI QIDQ4619465zbMATH OpenOpenAlexFDO

Authors Seungki Kim, Akshay Venkatesh

Publication date 6 February 2019

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

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

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)

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.

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

Cited in

(11)

• Volumes and distributions for random unimodular complex and quaternion lattices
• Random affine lattices
• Algorithmic Number Theory
• A physical study of the LLL algorithm
• Generating cryptographically-strong random lattice bases and recognizing rotations of \(\mathbb{Z}^n\)
• Improved Herrmann-May's attack with merging variables and lower LLL bound
• 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)