$\alpha$ of $I$ with $q_I(\alpha)$ prime, and return $I(\bar{\alpha}/N)$.

Assuming that numbers represented by $q_I$ behave like random numbers, it remains to ensure that $q_I([-m,m]^4)$ contains sufficiently many primes to have a high probability of finding one. If $\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\}$ is a Minkowski-reduced basis, the $q_I(\alpha_i)$ attain the successive minima, and we have the bounds $$p^2 \le 16 q_I(\alpha_1) q_I(\alpha_2) q_I(\alpha_3) q_I(\alpha_4) \le 4 p^2,$$ where $q_I(\alpha_i) \le q_I(\alpha_{i+1})$. For a generic ideal $I$ we expect $q_I(\alpha_4)$ to be in $\tilde{{O}}(\sqrt{p})$. In the worst case, $q_I(\alpha_4)$ is in $\tilde{{O}}(p)$ when $I$ equals an order ${\mathcal{O}}$ containing a subring $R$ with $|{\mathrm{disc}}(R)|$ in $O(\log(p)^n)$. Assuming $I$ is generic, we expect to find $\alpha$ with $q_I(\alpha)$ in $\tilde{{O}}(m^2 \sqrt{p})$. In practice, we find sufficiently many primes $q_I(\alpha)$ for $m$ which grows polynomially in $\log(p)$. However to provably terminate, even under the GRH, it may be necessary to allow $m$ to exceed a function in $O(\sqrt[4]{p})$, in which case the output may exceed $O(p)$.

We implemented a prime norm algorithm in Magma [@Magma]. We tested it on ideals of $\ell$-power norms generated via a random walk from a given maximal order. All our computations with primes of up to 200 bits and random ideals 