2
$\begingroup$

$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$.

Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector.

  1. If $GCD$ is in $NC$ and in particular if solving the linear Diophantine equation in two dimensions is in $NC$ then would it follow the two dimensional shortest vector problem is in $NC$?

  2. If $GCD$ is in $NC$ would it provide anything to shortest vector problem?

  3. More strongly if integer factoring is in $NC$ placing $GCD$ in $NC$ trivially, would it have any impact on shortest vector problem at least for fixed dimension?

Improve this question
$\endgroup$
12
  • $\begingroup$ Are questions 1 and 3 equivalent to asking whether an oracle for computing gcd(x,y) or for factoring makes this shortest-vector problem NC? $\endgroup$
    – Noam D. Elkies
    Commented Oct 5, 2022 at 2:44
  • $\begingroup$ Yes we can think of it that way.. Improve the $NC$ status of the shortest vector problem for $m=2$ and $m=O(1)$? And in general state something about shortest vector problem or approximation in general $m$ dimensions? $\endgroup$
    – Turbo
    Commented Oct 5, 2022 at 3:12
  • $\begingroup$ @NoamD.Elkies Gauss' reduction of binary quadratic forms is same as shortest vector computation in 2D. Correct? If not at least is there a relation between the two? $\endgroup$
    – Turbo
    Commented Oct 5, 2022 at 17:37
  • $\begingroup$ I'd expect that reduction of definite binary quadratic forms is like extended gcd, i.e. the computation not just of gcd(x,y) but of a,b such that gcd(x,y) = ax+by. It's not obvious to me how to get such a,b from the gcd in "NC". $\endgroup$
    – Noam D. Elkies
    Commented Oct 6, 2022 at 4:16
  • $\begingroup$ @NoamD.Elkies If GCD is in NC then if this problem cstheory.stackexchange.com/questions/51959/… is in NC we get $a,b$ in NC. From these can we say anything about $2$d svp and reduction of quadratic forms if GCD is in NC under reasonable assumptions? $\endgroup$
    – Turbo
    Commented Oct 6, 2022 at 14:54

0

Reset to default

You must log in to answer this question.