  For an elliptic curve with CM by $K$ defined over its Hilbert class field,
$E/H$, we extend Lenstra's finite fields test to generators of norms of certain
ideals in $\mathcal{O}_H$, yielding a sufficient $\widetilde{O}(\log^3 N)$
primality test and partially answering an open question of Lemmermeyer in the
case of CM elliptic curves. Letting $\iota,\gamma, b\in \mathcal{O}_K$,
$(\iota)$ prime, and $b$ a primitive $k$-th root of unity modulo $(\iota)^n$ we
specialize this test to rational integers of the form
$N_{K/\mathbb{Q}}(\gamma\iota^n+b)$ with the norm of $\gamma$ small, giving a
Las Vegas test for primality with average runtime $\widetilde{O}(\log^2 N)$,
that further certifies primality of such integers in $\widetilde{O}(\log^2 N)$
for nearly all choices of input parameters. The integers tested were not
previously amenable to quasi-quadratic heuristic primality certification.
