Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $n<<m$, $m=poly(n)$. One can assume $m$ is prime. Is there an efficient, possibly randomized, way to find an integer $N=poly(n)$, such that $(a_i \cdot N) (mod \ m)$ is approximately uniform on $[0,m]$. The value of $N$ may also depend on the approximation parameter.

• Should there be some additional hypothesis to prevent, for example, the situation where all the $a_i$ are equal? – Andreas Blass Jul 18 '13 at 14:52
• Yes, let's assume they are all different. – Lior Eldar Jul 18 '13 at 15:04
• "All different" won't work because there are $n$ of the integers $a_i$'s, all in $[0,m]$ with $m < n$ – Andreas Blass Jul 18 '13 at 15:08
• Of corse! - fixed the mistake above. – Lior Eldar Jul 18 '13 at 15:49

Choosing $N$ at random and checking should work. Put $e(t)=e^{2\pi i t/m}$. Then we have \begin{eqnarray*} \sum_{N=1}^m\sum_{k=1}^K\left|\sum_{i=1}^ne(k N a_i)\right|^2 & = & \sum_{N=1}^m\sum_{k=1}^K\sum_1\leq i,j\leq n e(kN(a_i-a_j))\\ & = & m\sum_{k\leq K} \#\{(i,j)|a_i\equiv a_j\pmod{\frac{m}{(m, k)}}\}. \end{eqnarray*} Since the $a_i$ are all different and in $[0, m]$, for fixed $a_i$ the number of $a_j$ satisfying the last congruence is $(m,k)$ at most, and the last sum is bounded above by $mn\sum_{k\leq K}(k,m)\leq mnK^2$.
Denote by $D_N$ the discrepancy of $a_iN\bmod m$. Then we have $$D_N\ll \frac{n}{K}+\sum_{k\leq K}\frac{1}{k}\left|\sum_{i=1}^n e(kNa_i)\right|,$$ thus $$\frac{1}{m}\sum_{N=1}^m D_N \ll \frac{n}{K} + \sqrt{nK}\log K.$$ Hence for most $N$ we have $D_N\ll n^{2/3}\log n$, which is reasonable good equidistribution.
Checking whether for a random $N$ we have that $D_N<n$ is small requires between $n^{1+\epsilon}$ and $n^{3/2}$ steps, depending on how small $D_N$ has to be.