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