we can appeal to average distributions among all arithmetic progressions $a - p\,[0,\Phi(M)]$, for representatives $a$ of $({\mathbb{Z}}/p{\mathbb{Z}})^*$. In the application that follows, $M$ will be of the form $\ell^e$ or $N\ell^e$, and we can adapt to failure to find primes in a particular arithmetic progression sparsely populated with primes by changing $e$.

Main algorithm {#sec:ideals:ellpow}
==============

In this section, we provide an algorithm to solve the quaternion $\ell$-isogeny path problem. We also sketch a generalization of our approach to build ideal class representatives with powersmooth norms.

Overview of the algorithm {#sec:algorithm_overview}
-------------------------

We reduce the quaternion $\ell$-isogeny problem to a restricted version of the same problem, where we assume that ${\mathcal{O}}$ is a special $p$-extremal maximal order with suborder $R + Rj$ as defined in Section \[sec:intro:QA\]. We also assume that $I$ is a left ${\mathcal{O}}$-ideal with reduced norm $N$, where $N$ is a (large) prime coprime to $\ell$, $|{\mathrm{disc}}(R)|$ and $p$. A reduction from generic left ${\mathcal{O}}$-ideals to left ${\mathcal{O}}$-ideals with the required norms can be effectively performed with the algorithm of Section \[sec:ideals:prime\]. A reduction from general maximal orders to special $p$-extremal orders will be provided in Section \[sec:ideals:gen\].

Using Lemma \[lem:ideal\_norm\_rep\], the quaternion $\ell$-isogeny path problem 