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$).
