order ${\mathcal{O}}$ in ${B_{p,\infty}}$ and a left ${\mathcal{O}}$-ideal $I$, compute an equivalent left ${\mathcal{O}}$-ideal $J = I\beta$ with norm $\ell^k$ for some $k$. This algorithm runs in practice in probabilistic polynomial time, and this effective runtime follows from heuristic assumptions on expected distributions of primes. With minimal adaptation, the algorithm also applies to output an ideal with smooth (or power-smooth) norm. The algorithm is described in terms of a special maximal order, but extends to any maximal order by passing through such a special order.

The motivation for this problem is an explicit equivalence of categories between left ${\mathcal{O}}$-ideals and supersingular elliptic curves (over $\bar{{\mathbb{F}}}_p$). The Deuring correspondence gives a bijection between such curves, up to Galois conjugacy, and isomorphism classes of maximal orders in ${B_{p,\infty}}$. This bijection can be turned into an equivalence of categories by the following construction. Let $E_0/K$ be a fixed elliptic curve with endomorphism ring ${\mathcal{O}}= {\mathrm{End}}(E_0)$ a quaternion order in ${B_{p,\infty}}= {\mathcal{O}}\otimes {\mathbb{Q}}$ (we may take the base field $K = {\mathbb{F}}_{p^2}$ and $E_0$ such that $|E_0(K)| = (p+1)^2$). Associated to any pair $(E_1,\varphi)$ where $\varphi: E_0 \rightarrow E_1$ is an isogeny, we obtain a left ${\mathcal{O}}$-ideal $I = \mathrm{Hom}(E_1,E_0) \varphi$ of norm $n 