Geodesic
The shortest vectors of lattices connected with a linear congruent generator
Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 88-109.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2004_16_4_a8,
     author = {A. S. Rybakov},
     title = {The shortest vectors of lattices connected with a linear congruent generator},
     journal = {Diskretnaya Matematika},
     pages = {88--109},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_4_a8/}
}
TY  - JOUR
AU  - A. S. Rybakov
TI  - The shortest vectors of lattices connected with a linear congruent generator
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 88
EP  - 109
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_4_a8/
LA  - ru
ID  - DM_2004_16_4_a8
ER  - 
%0 Journal Article
%A A. S. Rybakov
%T The shortest vectors of lattices connected with a linear congruent generator
%J Diskretnaya Matematika
%D 2004
%P 88-109
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2004_16_4_a8/
%G ru
%F DM_2004_16_4_a8
A. S. Rybakov. The shortest vectors of lattices connected with a linear congruent generator. Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 88-109. http://geodesic.mathdoc.fr/item/DM_2004_16_4_a8/

[1] Borevich Z. I., Shafarevich I. R., Teoriya chisel, Nauka, Moskva, 1985 | MR | Zbl

[2] Kassels Dzh. V. S., Vvedenie v geometriyu chisel, Mir, Moskva, 1965 | MR

[3] Koblits N., $p$-adicheskie chisla, $p$-adicheskii analiz i dzeta-funktsii, Bibfizmat, Mogilev, 1982 | MR

[4] Prakhar K., Raspredelenie prostykh chisel, Mir, Moskva, 1967 | MR

[5] Feldman N. I., Sedmaya problema Gilberta, Izd-vo MGU, Moskva, 1982 | MR

[6] Frieze A. M., Håstad J., Kannan R., Lagarias J. C., Shamir A., “Reconstructing truncated integer variables satisfying linear congruences”, SIAM J. Comput., 17:2 (1988), 262–280 | DOI | MR | Zbl

[7] Lagarias J. C., Lenstra H. W., Schnorr C. P., Korkine–Zolotareff bases and successive minima of a lattice and its reciprocal lattice, Tech. Rept., MSRI 07718-86, Math. Sci. Research Inst., Berkeley

[8] Waldschmidt M., Diophantine approximation on linear algebraic groups, Springer, Berlin, 1999 | MR | Zbl