An Indexing for Quadratic Residues Modulo $N$ and a Non-uniform Efficient Decoding Algorithm

Abstract

An \emph{indexing} of a finite set $S$ is a bijection $D:\{1,...,|S|\}\to S$. We present an indexing for the set of quadratic residues modulo $N$ that is decodable in polynomial time on the size of $N$, given the factorization of $N$. One consequence of this result is a procedure for sampling quadratic residues modulo $N$, when the factorization of $N$ is known, that runs in strict polynomial time and requires the theoretical minimum amount of random bits (i.e., $\log (\varphi (N)/2^r)$ bits, where $\varphi (N)$ is Euler's totient function and $r$ is the number of distinct prime factors of $N$). A previously known procedure for this same problem runs in expected (not strict) polynomial time and requires more random bits.