The relaxed approximation problem is to search for $\lambda$ in ${\mathbb{Z}}$ and $\mu_1 = x_1 + y_1 \omega + (z_1 + w_1 \omega) j$ such that $\mu = \lambda\mu_0 + N\mu_1$ satisfies the norm equation $${\mathrm{Nrd}}(\mu) = 
    f(\lambda x_0 + N x_1, \lambda y_0 + N y_1) + 
p\, f(\lambda z_0 + N z_1, \lambda w_0 + N w_1) = \ell^e,$$ for some $e\in\mathbb{N}$, where $f(x,y) = {\mathrm{Nrd}}(x + y\omega)$ is a principal binary quadratic form of discriminant $D$ as in Lemma \[lem:special-p-extremal-properties\]. The key idea to solve this norm equation, as used in [@Petit2008c] to cryptanalyze the other hash function of Charles-Goren-Lauter, is that it simplifies considerably when $x_0 = y_0 = 0$: $$\label{eq:simplified-normequation}
{\mathrm{Nrd}}(\mu) = N^2 f(x_1, y_1) + p\, f(\lambda z_0 + N z_1, \lambda w_0 + N w_1) = \ell^e.$$ The simple algorithm we now describe to solve this equation justifies the choice of $[\mu] \in (R/NR)^*[j]$ in Section \[sec:ideals:ellpow:isom\].

To construct $\mu$, given $[\mu] \in (R/NR)^*[j]$, we consider a first lift $\mu_0 = (z_0 + w_0 \omega) j$ to $Rj$ as above, and find $\lambda$ in ${\mathbb{Z}}$ and $\mu_1  = (x_1 + y_1 \omega) + (z_1 + w_1 \omega) j$ in $R + Rj$ satisfying 