Suponga que tiene un conjunto $S\subset\mathbb{Z}[x,y].$ ¿Cómo se pueden dividir eficazmente los polinomios en conjuntos de manera que los primos representados por los polinomios en cualquier conjunto sean idénticos? A estos efectos, "eficiente" puede interpretarse como "subcuadrático", aunque me interesa tanto el caso práctico como el teórico/peor.
Un caso especial de especial interés: las formas cuadráticas binarias $ax^2+bxy+cy^2.$
Para cualquier par de polinomios, es posible comprobar si los dos son formas equivalentes. Por supuesto, esto requiere comprobar cuadráticamente muchos pares. Una forma práctica de acelerar el proceso sería dividir primero los polinomios por discriminante, en el caso de las formas cuadráticas binarias, $b^2-4ac.$ Esto sólo requiere un tiempo (esencialmente) lineal, y da lugar a una aceleración por un factor de $k$ si hay $k$ discriminantes con un número aproximadamente igual de polinomios para cada uno (tiempo $n^2/k^2$ para cada discriminante, $k$ discriminantes). ¿Existen otros invariantes que puedan utilizarse de forma similar?