HJLS algorithm ( Integer Relation)

Time Complexity

$O(n^{3}(n+k))$

Space Complexity

$O(n^{2})$ -- but requires infinite precision with large n or else it becomes unstable bits

(Derived: Store Gram-Schmidt basis vectors b_i (n n-dimensional vectors) and Gram-Schmidt numbers \mu_{i,j} (i and j both from 1 to n), not sure how to take into account the "bit complexity" part)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

bit complexity

Year

1986

Reference

https://epubs-siam-org.ezproxy.canberra.edu.au/doi/pdf/10.1137/0218059