Factoring Polynomials via the Splitting Circle Method

 Abstract: Finding the roots of a polynomial is an ill-conditioned problem that requires numerical methods in the general case. Unfortunately, most existing numerical methods do not guarantee convergence when working in finite precision. Schonhage (1971) uses some methods from complex analysis to guarantee convergence to the roots in the finite precision case. We describe our implementation of Schonhage’s algorithm, largely based off of Xavier Gourdon’s description (1996).

Share this Event