Congruence arithmetic algorithms for polynomial real zero determination

摘要

This paper describes a set of algorithms for isolating the real zeros of a univariate polynomial with integer coefficients. The algorithms employ congruence (modular, finite field) arithmetic and are analogous to a set of integer arithmetic algorithms described by the author in a recent paper. The algorithms are analyzed to bound their computing times and these computing times are compared to the computing times of the integer arithmetic algorithms. Some empirical computing times are reported.