On the Representation of Primes by Binary Quadratic Forms

The old problem of computing the representation of a prime p by a given quadratic form of discriminant ∆ is considered. This representation problem is shown to be solvable, under mild technical conditions, in polynomial complexity with respect to p. Further, a method is proposed which obtains the explicit representation of p by the integer roots of univariate polynomials