Let $n \in \mathbb{N}$. Let $R_n$ be the set of quadratic residues in $\mathbb{Z}/n\mathbb{Z}$. Suppose we are given access to a factorization for $n$ into prime powers $n = \prod_{i=1}^k p_i^{e_i}$. Is there a way to list all elements of $R_n$ in $O(|R_n|)$ time? Clearly one can square all $m$ in $1 \le m \le \lceil\frac{n}{2}\rceil$, but if $|R_n| \ll n$ this can be prohibitive.
If that's too hard, since $|R_n| = \prod_{i=1}^k |R_{p_i^{e_i}}|$, suppose we were given some precomputation time for each $p_i^{e_i} < N$, for some upper bound $N$, where $n < N$, and we had to list $R_n$ for several such $n$ (allowing us to amortize some of the precomputation). Could we then more quickly solve the Chinese Remainder Theorem systems $\{ x \equiv r_i \pmod{p_i^{e_i}}\}$, for each tuple $(r_1, \dots, r_k)$ such that $r_i$ is in $R_{p_i^{e_i}}$, which would yield each $x \in R_n$?