# Partitioning polynomials in $\mathbb{Z}[x,y]$ by the primes they represent

Suppose you have a set $S\subset\mathbb{Z}[x,y].$ How can one efficiently partition the polynomials into sets such that the primes represented by the polynomials in any given set are identical? For these purposes, "efficient" can be interpreted as "subquadratic", though I'm interested in practical as well as theoretical/worst-case.

A special case of particular interest: binary quadratic forms $ax^2+bxy+cy^2.$

For any pair of polynomials, it's possible to check if the two are equivalent forms. Of course this requires checking quadratically many pairs. One practical speedup would be to first partition the polynomials by discriminant—in the case of binary quadratic forms, $b^2-4ac.$ This takes only (essentially) linear time, and results in speedup by a factor of $k$ if there are $k$ discriminants with roughly equal numbers of polynomials for each (time $n^2/k^2$ for each discriminant, $k$ discriminants). Are there further invariants that can be used in similar fashion?

-
A good reference might be David Cox's "Primes of the Form x^2+ny^2." He discusses some applications of genus theory, class field theory, and complex multiplication to this kind of problem. – Tony Mar 21 '11 at 2:52

First partition the polynomials $ax^2+bxy+cy^2$ by their discriminant $\Delta=b^2-4ac$, as mentioned in the question. Polynomials with $\Delta>0$ have a unique reduced form, that is, can be represented uniquely as $ax^2+bxy+cy^2$ with $$\left|\sqrt\Delta-2|c|\right|<b<\sqrt\Delta$$
Polynomials with negative discriminant have only finitely many forms with $$|b|\le a\le c$$ (To be reduced, $b\ge0$ if $a\in\{|b|,c\},$ but of course finitude does not depend on this.) It's not clear that this is practical when comparing forms; it depends on the size of the coefficients and the number of forms of a given discriminant.
Of course since only the primes in those discriminants are desired, certain transformations can be made that would otherwise be impermissible. For example, polynomials with non-unitary content $c$ can be reduced to either $\{c\}$ or $\emptyset$ as appropriate. Broadening slightly to binary quadratic polynomials, parity substitutions can be made: $$x^2+2y^2\mapsto (2x+1)^2+2y^2$$