took seconds on an Intel Xeon CPU X5500 processor with 24 GB RAM running at 2.67GHz. The norms of the output ideals $J$ were experimentally only slightly larger than $\sqrt{p}$. The experimental results are given in Appendix \[sec:primeres\].

Representing integers by special orders {#sec:repns_in_orders}
---------------------------------------

We also consider the problem of representing a sufficiently large positive integer $M$ by the norm form of ${\mathcal{O}}$. Suppose that ${\mathcal{O}}$ is a $p$-extremal order, with suborder $R + Rj$, and let $D = {\mathrm{disc}}(R)$. We let $\Phi(x)$ be a monotone function such that a suitable interval $[x,x+\Phi(x)]$ contains sufficiently many primes, and we assume that $M \ge p\,\Phi(M)$. If $\omega$ is a reduced generator of $R$ (of trace $0$ or $\pm 1$), then the norm form on $R + Rj$ is of the form $${\mathrm{Nrd}}(\alpha + \beta j) = f(x_1,y_1) + p f(x_2,y_2),$$ where $\alpha = x_1 + y_1 \omega$ and $\beta = x_2 + y_2 \omega$, and $f(x,y)$ is a principal form. For $(x,y)$ in $[-m,m]^2$ with $m = \lfloor\sqrt{\Phi(M)/|D|}\rfloor$, we have $f(x,y) < \Phi(M)$ and ${\mathrm{Nrd}}(\beta j) < p\,\Phi(M) < M$. This gives the following algorithm on which we build our strong approximation algorithm.

[**Integer representation.**]{} Given an integer $M \ge 