On Testing a Bivariate Polynomial for Analytic Reducibility

LetKbe an algebraically closed field of characteristic zero. We present an efficient algorithm for determining whether or not a given polynomialf(x,y) inK[x,y] is analytically reducible overKat the origin. The algorithm presented is based upon an informal method sketched by Kuo (1989) which is in turn derived from ideas of Abhyankar (1988). The presentation contained herein emphasises the proofs of the algorithmʹs correctness and termination, and is suitable for computer implementation. A polynomial worst case time complexity bound is proved for a partial version of the algorithm.