Integer Relation Among Integers (Integer Relation)

From Algorithm Wiki
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