Computingxmmodp(x)and an Application to Splitting a Polynomial Into Factors Over a Fixed Disc

Koenigʹs theorem is a well-known basis for fast splitting a polynomial into factors over a fixed disc in the complex plane. We simplify the computation of such factors by means of its reduction to solving a banded triangular Toeplitz linear system of equations. The technique used may be of some interest in its own right, in particular, due to its possible extension to computing a power modulo a polynomial.