On the Representation of Primes by Binary Quadratic Forms, and Elliptic Curves

It is shown that, under some mild technical conditions, representations of
prime numbers by binary quadratic forms can be computed in polynomial
complexity by exploiting Schoof's algorithm, which counts the number of
$\mathbb F_q$-points of an elliptic curve over a finite field $\mathbb F_q$.
Further, a method is described which computes representations of primes from
reduced quadratic forms by means of the integral roots of polynomials over
$\mathbb Z$. Lastly, some progress is made on the still-unsettled general
problem of deciding which primes are represented by which classes of quadratic
forms of given discriminant.