2
$\begingroup$

Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod $p$)? If we think of the $n$ values as a vector $\vec a\in Z_p^n$, I want to know if there is a way to find the point on the line spanned by $\vec a$ which has minimum $\ell_\infty$ norm.

Of course when $p$ is small, one can simply examine all values of $\alpha\in Z_p$, however I am wondering whether there is a polynomial time (in $n$) algorithm even for large values of $p$ (say $p\approx 2^n$).

$\endgroup$
1
  • 2
    $\begingroup$ This amounts to finding a short vector in the lattice in $\mathbb Z^n$ generated by the $n+1$ vectors $(a_1,\ldots,a_n),(p,0,\ldots,0),(0,p,\ldots,0),\ldots,(0,0,\ldots,p)$. The LLL algorithm might help. $\endgroup$ May 19, 2015 at 16:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.