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?