# Algorithm for determining whether two polynomials have the same splitting field

This question asks how to tell whether two cubic polynomials with coefficients in $\mathbb{Q}$ have the same splitting field. There are several answers to the question, but they don't include proofs. Also, it's not clear how the results generalize to higher degree polynomials. Is there an algorithm for determining whether two polynomials in in $\mathbb{Q}[x]$ have the same splitting field? If so, what is it, and why does it work?

(Reposted from Math Stack Exchange.)

-
This question just boils down to the question of whether a polynomial with coefficients in a given number field has a root (apply this repeatedly), and there are algorithms for this -- see e.g. Cohen's "a course in number theory and cryptography". –  user30035 Dec 31 '12 at 8:52

In practice, you can reduce f and g mod the first 1000 primes (deleting those where f and g are ramified) and see if the primes all have the same splitting behavior. If they don't, the splitting fields are not the same, and if they do, you can be pretty darn sure that they are. If you want to replace "be pretty darn sure" with "have proved" you can use the effective Chebotarev of Lagarias and Odlyzko to figure out the value of 1000 which actually gives you a proof.

-
So, does this rigorously establish a randomized polynomial time algorithm for the original question, assuming GRH? –  Greg Kuperberg Jan 1 '13 at 22:33
Depends what the bounds in Lagarias-Odlyzko are and I don't have them in my head right now. You might look at a recent paper of Kowalski and Zywina which carries out a computation of this kind in real life. –  JSE Jan 2 '13 at 1:53
+1 for "the value of 1000 which actually gives you a proof" –  Filippo Alberto Edoardo Jan 2 '13 at 4:37
This is nice. I don't immediately see why the effective Chebotarev density theorem tells you when you're done. But it's nice. wccanard's answer seems potentially more conceptually primitive, but I guess one would need to take a close look at the algorithm to be sure. –  Jonah Sinick Jan 2 '13 at 4:51