The old problem of computing the representation of a prime p by a given quadratic form of discriminant D 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.

quadratic field, binary quadratic form, representation of primes, Hilbert class polynomial, elliptic curve.