Integer Relation Among Integers: Difference between revisions

Latest revision as of 08:24, 10 April 2023

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

@@ Line 10: / Line 10: @@
 == Parameters ==
-n: dimensionality of vectors
+$n$: dimensionality of vectors
 == Table of Algorithms ==
@@ Line 20: / Line 20: @@
 |-
-| [[HJLS algorithm ( Integer Relation)|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 || [https://epubs.siam.org/doi/pdf/10.1137/0218059 Time]
+| [[HJLS algorithm ( Integer Relation)|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 || [https://epubs.siam.org/doi/pdf/10.1137/0218059 Time]
 |-
 |}