The shortest vectors of lattices connected with a linear congruent generator
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 378910973 | ||
| 003 | CHVBK | ||
| 005 | 20180305123541.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 161128e20041001xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1515/1569392042572203 |2 doi |
| 035 | |a (NATIONALLICENCE)gruyter-10.1515/1569392042572203 | ||
| 100 | 1 | |a Rybakov |D A. S. | |
| 245 | 1 | 4 | |a The shortest vectors of lattices connected with a linear congruent generator |h [Elektronische Daten] |c [A. S. Rybakov] |
| 520 | 3 | |a Let ε > 0 be a fixed real number, ⊂ R s be a full rank lattice with determinant Δ ∈ Q. We call this lattice ε-regular if λ 1 () > Δ1/s (h(Δ))-ε , where λ1() is the length of the shortest nonzero vector of and h(Δ) is the maximum of absolute values of the numerator and the denominator of the irreducible rational fraction for Δ. In this paper, we consider two full rank lattices in the space R s : the lattice ℒ(a, W) connected with the linear congruent sequence (x N ), x N +1 = ax N (mod W), N =1 ,2, . . . , (1) and the lattice ℒ∗ (a, W) dual to ℒ(a, W). There is a conjecture which states that for any natural number s, any real number 0 < ε < ε 0(s), and any natural number W > W 0 (s, ε), the lattices ℒ(a, W) and ℒ∗(a, W) are ε-regular for all a = 0 ,1, . . . , W - 1 excluding some set of numbers a of cardinality at most W 1-ε . 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 W1- ε/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. | |
| 540 | |a Copyright 2004, Walter de Gruyter | ||
| 773 | 0 | |t Discrete Mathematics and Applications |d Walter de Gruyter |g 14/5(2004-10-01), 479-500 |x 0924-9265 |q 14:5<479 |1 2004 |2 14 |o dma | |
| 856 | 4 | 0 | |u https://doi.org/10.1515/1569392042572203 |q text/html |z Onlinezugriff via DOI |
| 908 | |D 1 |a research article |2 jats | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1515/1569392042572203 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 100 |E 1- |a Rybakov |D A. S. | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Discrete Mathematics and Applications |d Walter de Gruyter |g 14/5(2004-10-01), 479-500 |x 0924-9265 |q 14:5<479 |1 2004 |2 14 |o dma | ||
| 900 | 7 | |b CC0 |u http://creativecommons.org/publicdomain/zero/1.0 |2 nationallicence | |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-gruyter | ||