p\,\Phi(M)$. Set $m = \lfloor\sqrt{\Phi(M)/|D|}\rfloor$, and choose $(x_2,y_2)$ at random in $[-m,m]^2$ until finding a prime $r = M - p f(x_2,y_2)$ which is split in $R$ and for which a prime $\mathfrak{r}$ over $r$ is principal. Let $\alpha = x_1 + y_1 \omega$ be a generator for $\mathfrak{r}$, set $\beta = x_2 + y_2 \omega$, and return $\alpha + \beta j$.

Clearly the output has norm $M$. We assume that primes have density $1/\log(M)$ in the arithmetic progression $M - p\,[0,\Phi(M)]$. Moreover we assume that such primes are equidistributed among primes which are non-split and split in $R$ and, in the latter case, among each of the $h(R)$ ideal classes of $R$. Finally, we must assume that elements $\beta = x_2 + y_2 \omega$ give rise to integers $r = M - p\,{\mathrm{Nrd}}(\beta)$ with the same primality probabilities as random integers in the range $M - p\,[0,\Phi(M)]$. Under such heuristic assumptions, the expected number of random $\beta$ to be tested is $2 h(R) \log(M)$. Detecting a prime $r$, solving for a representative prime $\mathfrak{r}$ over $r$, and determination of a principal generator can be done in expected polynomial time by Cornaccia’s algorithm [@Cornacchia1903].

Under the heuristic assumptions made above, 