Skip to main content
deleted 2 characters in body
Source Link
Lior Eldar
  • 445
  • 2
  • 8

Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $m<<n$$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.

Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $m<<n$, $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.

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.

Source Link
Lior Eldar
  • 445
  • 2
  • 8

Spreading-out integers via multiplication

Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $m<<n$, $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.