Evaluation of linear relations between vectors of a lattice in Euclidean space (Q3840173)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1186951
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Evaluation of linear relations between vectors of a lattice in Euclidean space |
scientific article; zbMATH DE number 1186951 |
Statements
20 July 1999
0 references
lattices over the reals
0 references
linear independence
0 references
continued fractions
0 references
number theoretic algorithms
0 references
discrete logarithms
0 references
complexity
0 references
0.7689793705940247
0 references
0.765739381313324
0 references
Evaluation of linear relations between vectors of a lattice in Euclidean space (English)
0 references
Let \(L\) be a \(k\)-dimensional lattice over \({\mathbb R}^n\) with \(k\leq n\). This paper presents an algorithm for finding a linear dependence, if it exists, among a set of \(m\) vectors of \(L\). The complexity of this algorithm is \(O(n^{5+\varepsilon}(\log Mn/\lambda)^{1+\varepsilon})\), where \(M\) is an upper bound on the Euclidean length of the vectors, and \(\lambda\) is the first successive minimum of \(L\). This is an improvement over an algorithm due to \textit{D. M. Gordon} [SIAM J. Discrete Math. 6, 124-138 (1993; Zbl 0772.11046)], and has applications in computing discrete logarithms over finite fields. The author makes use of convergents to approximate real numbers. For the entire collection see [Zbl 0891.00022].
0 references