We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Sieve algorithms for some orthogonal integer lattices.
- Authors
Tchinda, Arnaud Gires Fobasso; Fouotsa, Emmanuel; Jugnia, Celestin Nkuimi
- Abstract
We propose in this work a Sieve algorithm that we called OrthogonalInteger sieve algorithm for some orthogonal integer lattices and particularly the case of integer lattices Λ ⊂ ℤ n , root lattices of type A n (n ≥ 1) and of type D n (n ≥ 2). In these cases, we use the famous L L L algorithm to find the shortest vector of these lattices. Indeed, in general, a sieve algorithm builds a list of short random vectors which are not necessarily in the lattice, and try to produce short lattice vectors by taking linear combinations of the vectors in the list. But in our case, we built a list of short vectors in the lattice. From the first column of the L L L -reduced basis of the considered basis, we have the list of at least n and at most 2 n short vectors for the general case (where n is the dimension of the lattice) of orthogonal integer lattices Λ ⊂ ℤ n . For the lattices ℤ n , A n (n ≥ 1) and D n (n ≥ 2), we have, respectively, 2 n , n (n + 1) and 2 n (n − 1) short vectors. The proposed sieve algorithm for integer lattice ℤ n runs in space O (2 n) and the OrthogonalInteger sieve algorithm performs O (n 2 n) arithmetic operations and is polynomial in space.
- Subjects
SIEVES; RIESZ spaces; ARITHMETIC; ALGORITHMS
- Publication
Discrete Mathematics, Algorithms & Applications, 2023, Vol 15, Issue 7, p1
- ISSN
1793-8309
- Publication type
Article
- DOI
10.1142/S1793830922501518