Integer Relation Among Integers (Integer Relation)

Description

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$

$n$: dimensionality of vectors

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