I imagine the quadratic form f in Fred's post is over the integers. If Z = the integers then f : Z x Z —> Z via f(x, y) = a x^2 + b x y + c y^2 with a, b, c in Z. And that "binary" quadratic form just means that it's in 2 variables — right? Question (probably for Victor): What are appropriate definitions of equivalence of such quadratic forms? I would think that we would say that the quadratic forms f and g over Z are "equivalent over Z" if there is an invertible matrix (P Q) M = ( ) of integers P, Q, R, S such that by abuse of notation, (R S) f(M(x, y)') = g(x, y), for all column vectors (x, y)' in Z. Or non-abusively f(Px+Qy, Rx+Sy) = g(x, y). Then: What is a set containing one simple representative for each equivalence class? Is it finite? And: Given an arbitrary quadratic form f as above: What is a simple way to determine which of these representatives it is equivalent to? This could be used to simplify the process of determining which numbers are represented by a given quadratic form f. If say f is equivalent over Z to the standard representative g_k, then it represents the same integers as g_k, which can be known in advance. How does the equivalence relation, and standard representatives, change if the coefficients {P, Q, R, S} can be any rational numbers? —Dan ----- I spent most of the weekend failing to adapt Will Jagy's algorithm, encouraged by a delusion that I understood better why that should work. Once that notion had been dispelled, Victor's method succeeded at once, and generalises to an arbitrary quadratic form as follows. (A) To represent a prime number p by a quadratic form f(x, y) : (1) Solve quadratic equation f(w, 1) = 0 over |F_p ; (2) Reduce the lattice basis { [w, 1], [p, 0] } to a minimal basis; (3) Now either reduced vector yields [s, t] such that f(s, t) = p . The second quadratic root actually applies to the conjugate form, so that signs in step (3) may be incorrect. Efficient polynomial-time algorithms are eg. Tonelli-Shanks for step (1), and enhanced Euclidean for step (2). However, one's favourite CAS these days conceals such drudgery behind clean facades, such as Magma's Sqrt() and LLL() . Useful test info is available at http://oeis.org/wiki/User:Peter_Luschny/BinaryQuadraticForms There remain two supplementary questions. (B) Exactly why does method (A) work? (C) How do representations of prime factors combine into representations of a composite target? All these seem bread-and-butter questions to my innocent mind, and it is mystifying that they are not part-and-parcel of standard treatments. Or are they? Fred Lunnon On 4/14/18, Victor Miller <victorsmiller@gmail.com> wrote:

Yes, See my answer to the question about the sum of two squares:

https://mathoverflow.net/questions/70208/system-of-diophantine-equations?rq=...

For your problem you need to find a primitive 6th root of unity (really just finding sqrt(-3)), then set up the lattice and apply LLL.

Fred Lunnon <fred.lunnon@gmail.com> wrote:

...

There exists an algorithm for finding integers m,n such that x = m^2 + n^2 , in amortised time proportional to (log x)^3 , where x is prime with x mod 4 = 1 . See Richard E. Crandall, Carl Pomerance "Prime Numbers: A Computational Perspective" Springer (2001), sect 2.3.2 pp 93--96 .

Is there an analogous efficient algorithm for x = m^2 + m n + n^2 ? See https://en.wikipedia.org/wiki/Eisenstein_integer https://oeis.org/A034017 , https://oeis.org/A000086

What about more general binary quadratic forms?