RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2004 Volume 16, Issue 4, Pages 88–109 (Mi dm178)

This article is cited in 2 papers

The shortest vectors of lattices connected with a linear congruent generator

A. S. Rybakov


Abstract: Let $\varepsilon>0$ be a fixed real number, $\mathcal E\subset\mathbf R^s$ be a full rank lattice with determinant $\Delta\in\mathbf Q$. We call this lattice $\varepsilon$-regular if $\lambda_1(\mathcal E)>\Delta^{1/s}(h(\Delta))^{-\varepsilon}$, where $\lambda_1(\mathcal E)$ is the length of the shortest nonzero vector of $\mathcal E$ and $h(\Delta)$ is the maximum of absolute values of the numerator and the denominator of the irreducible rational fraction for $\Delta$. In this paper, we consider two full rank lattices in the space $\mathbf R^s$: the lattice $\mathcal L(a,W)$ connected with the linear congruent sequence
\begin{equation} (x_N),\quad x_{N+1}=ax_N\pmod W,\quad N=1,2,\ldots, \end{equation}
and the lattice $\mathcal L^*(a,W)$ dual to $\mathcal L(a,W)$.
There is a conjecture which states that for any natural number $s$, any real number $0<\varepsilon<\varepsilon_0(s)$, and any natural number $W>W_0(s,\varepsilon)$, the lattices $\mathcal L(a,W)$ and $\mathcal L^*(a,W)$ are $\varepsilon$-regular for all $a=0,1,\ldots,W-1$ excluding some set of numbers $a$ of cardinality at most $W^{1-\varepsilon}$.
In the case $s=3$, A. M. Frieze, J. Hestad, R. Kannan, J. C. Lagarias, and A. Shamir in a paper published in 1988 proved a more weak assertion (in their estimate the number of exceptional values $a$ is at most $W^{1-\varepsilon/2}$). Using the methods of this paper, it is not difficult to prove the conjecture for $s=1$ and $s=2$.
In our paper, we prove the conjecture for $s=4$. With the help of our methods we improve the result of the paper mentioned above and prove the conjecture for $s=3$.
Our result can be applied to the reconstruction of a linear congruent sequence (1) if the high-order bits of its first $s$ elements are given.

UDC: 519.7

Received: 10.11.2003
Revised: 14.09.2004

DOI: 10.4213/dm178


 English version:
Discrete Mathematics and Applications, 2004, 14:5, 479–500

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025