RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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.

DOI: https://doi.org/10.4213/dm178

Full text: PDF file (1784 kB)
References: PDF file   HTML file

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

Bibliographic databases:

UDC: 519.7
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

Citation in format AMSBIB
\Bibitem{Ryb04}
\by A.~S.~Rybakov
\paper The shortest vectors of lattices connected with a linear congruent generator
\jour Diskr. Mat.
\yr 2004
\vol 16
\issue 4
\pages 88--109
\mathnet{http://mi.mathnet.ru/dm178}
\crossref{https://doi.org/10.4213/dm178}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2141148}
\zmath{https://zbmath.org/?q=an:1111.11033}
\transl
\jour Discrete Math. Appl.
\yr 2004
\vol 14
\issue 5
\pages 479--500
\crossref{https://doi.org/10.1515/1569392042572203}


Linking options:
  • http://mi.mathnet.ru/eng/dm178
  • https://doi.org/10.4213/dm178
  • http://mi.mathnet.ru/eng/dm/v16/i4/p88

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Number of views:
    This page:268
    Full text:109
    References:15
    First page:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019