A physical study of the LLL algorithm (Q2112788)

The \(\mathrm{LLL}\)-algorithm [\textit{A. K. Lenstra} et al., Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)] is a very powerful algorithmic with several applications to computational science, and cryptography. The purpose of this paper is to show how statistical physics might permit a scientific approach to the empirical behavior of the \(\mathrm{LLL}\) algorithm by considering it as a sandpile model. The authors establish a ``matching sandpile phenomena'' for each \(\mathrm{LLL}\) phenomenon, the majority of which are either already known to physicists or recorded by well-known physics methods. These ideas seem to present challenges to physics, and will inspire rich and fruitful interdisciplinary interactions centered on the \(\mathrm{LLL}\)-algorithm and lattice reduction techniques in general. The authors present some stochastic sandpile models that are close to \(\mathrm{LLL}\)-algorithm. They introduce an \(\mathrm{LLL-SP}\)-algorithm and an \(\mathrm{S S P}\)-algorithm respectively. They show that for \(RHF\) gap phenomenon, in all sufficiently large system sizes (which corresponds to the lattice dimensions for \(\mathrm{LLL}\)-algorithm), there exists a gap between the worst-case and the average-case \(RHF\)s of \(\mathrm{S S P}\). ``Finite-Size Scaling theory (\(\mathrm{FSS}\))'' is a theory in physics that studies critical phase transitions, such as water freezing into ice, and metals being magnetized. The authors of this paper establish a connection between the \(LLL\)-algorithm and sandpile models by applying \(\mathrm{FSS}\) to \(\mathrm{LLL}\). The current paper is significantly different from what is known in the cryptographic literature. The achieved results are consequence of an elegant combination of techniques from ``algorithmic number theory'', ``cryptography'' and ``statistics and probability''.