the multiplicativity of the reduced norm, and ${\mathrm{Nrd}}(\alpha) = {\mathrm{Nrd}}(\bar{\alpha})$, we have $${\mathrm{Nrd}}(I\gamma) = {\mathrm{Nrd}}(I){\mathrm{Nrd}}(\gamma) 
= N\frac{{\mathrm{Nrd}}(\alpha)}{N^2} = \frac{{\mathrm{Nrd}}(\alpha)}{N} = q_I(\alpha).$$ Clearly $I$ is a fractional left ${\mathcal{O}}$-ideal, so it remains to show that $I\gamma \subseteq {\mathcal{O}}$. Since ${\mathcal{O}}\alpha \subseteq I$, we have $\bar{\alpha} \subseteq \bar{I}$, and hence $I\bar{\alpha} \subseteq I\bar{I} = N{\mathcal{O}}$, from which $I\gamma \subseteq {\mathcal{O}}$ follows.

Preliminary algorithmic results\[sec:prel\]
===========================================

In this section, we provide two algorithmic tools that will be used to solve the quaternion $\ell$-isogeny path problem in Section \[sec:ideals:ellpow\]. The first algorithm computes prime norm representatives in ideal classes. The second one computes representations of integers by the norm form of a $p$-extremal order.

Computing prime norm representatives in ideal classes {#sec:ideals:prime}
-----------------------------------------------------

Given a maximal order ${\mathcal{O}}$ and a left ${\mathcal{O}}$-ideal $I$, we give a probabilistic algorithm that computes another left ${\mathcal{O}}$-ideal $J = I\gamma$ in the same class, but with prime norm. Using Lemma \[lem:ideal\_norm\_rep\], this problem reduces to the problem of finding a prime represented by $q_I$.

[**Prime norm algorithm.**]{} Given a left ${\mathcal{O}}$-ideal $I$ of norm $N$, with a Minkowski-reduced basis $\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\}$. Generate random elements $\alpha = \sum_i x_i \alpha_i$ with $(x_1,x_2,x_3,x_4)$ in a box $[-m,m]^4$ until finding an element 