note that $(R/NR)^*$ acts on the $N+1$ proper nontrivial left ${\mathcal{O}}$-ideals, with kernel $({\mathbb{Z}}/N{\mathbb{Z}})^*$. By hypothesis, $R$ is a subring of small discriminant in which $N$ is not ramified. If $N$ is inert in $R$, then the $N+1$ ideals form one orbit. Otherwise, if $N$ is split, there is one orbit of size $N-1$ and two fixed points ${\mathcal{O}}{\mathfrak{p}}_1/N{\mathcal{O}}$ and ${\mathcal{O}}{\mathfrak{p}}_2/N{\mathcal{O}}$, where ${\mathfrak{p}}_1$ and ${\mathfrak{p}}_2$ are the prime ideals of $R$ over $N$. With overwhelming probability, $I/N{\mathcal{O}}$ and ${\mathcal{O}}\gamma/N{\mathcal{O}}$ will not be such fixed points, and so we can solve for $[\mu]$ in $(R/NR)^*[j]$. In the event of failure, we can select a new $\gamma$ or $N$.

Approximating elements of $(R/NR)^*[j]$ by $\ell$-power norm representatives {#sec:ideals:ellpow:lift}
----------------------------------------------------------------------------

In this section, we assume that $\ell$ is a quadratic non-residue modulo $N$. Let also $\omega$ be a generator of $R$ of minimal norm, either $1$, $2$, or $(1+q)/4$, for $q$ a prime congruent to $3$ modulo $4$. We now motivate the restriction to elements of $(R/NR)^*[j]$ in the previous section.

We suppose that we are given as input a lift $\mu_0 = x_0 + y_0 \omega + (z_0 + w_0 \omega) j$ of an arbitrary element of ${\mathcal{O}}/N{\mathcal{O}}$ to $R + Rj$. 