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 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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references