We provide an irreducibility test in the ring Kxy whose complexity is quasi-linear with respect to the discriminant valuation, assuming the input polynomial F is square-free and K is a perfect field of characteristic not dividing deg(F). The algorithm uses the theory of approximate roots and may be seen as a generalisation of Abhyankar's irreducibility criterion to the case of non-algebraically closed residue fields.
展开▼