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: I will address the special case of binary quadratic forms.  Some of this applies more generally.
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$$
So within a given positive discriminant, equivalent forms can be collected immediately.
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$$
