Integer Relation Among Integers (Integer Relation)

From Algorithm Wiki
Revision as of 08:24, 10 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Given a vector $x \in \mathbb{Z}^n$, find an integer relation, i.e. a non-zero vector $m \in \mathbb{Z}^n$ such that $<x, m> = 0$

Related Problems

Generalizations: Integer Relation Among Reals


$n$: dimensionality of vectors

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
HJLS algorithm 1986 $O(n^{3}(n+k))$ $O(n^{2})$ -- but requires infinite precision with large n or else it becomes unstable Exact Deterministic Time