|
This article is cited in 2 scientific papers (total 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.
Received: 10.11.2003 Revised: 14.09.2004
Citation:
A. S. Rybakov, “The shortest vectors of lattices connected with a linear congruent generator”, Diskr. Mat., 16:4 (2004), 88–109; Discrete Math. Appl., 14:5 (2004), 479–500
Linking options:
https://www.mathnet.ru/eng/dm178https://doi.org/10.4213/dm178 https://www.mathnet.ru/eng/dm/v16/i4/p88
|
Statistics & downloads: |
Abstract page: | 454 | Full-text PDF : | 262 | References: | 33 | First page: | 5 |
|