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.
I. INTRODUCTION
In a recent paper [6], the author presented and analyzed a set of algorithms employing integer arithmetic which solved the following problems for all univariate polynomials with integer coefficients: (1) given a polynomial P with possible multiple zeros, compute a polynomial Q with the same zeros as P but which only occur as simple zeros, (2) determine the total number of real zeros of a polynomial with only simple zeros, (3) determine the number of real zeros in a specified interval of a polynomial with all simple zeros, (4) isolate the real zeros of a polynomial with all simple zeros, and (5) refine the real zeros of a polynomial with all simple zeros until the error in them is less than some arbitrary positive rational number. By isolation of the real zeros of a polynomial is meant the process of finding real intervals 11, I s ..... Ik such that each interval Ii, 1 ~ i ~ k, contains exactly one real zero of the polynomial, and every real zero of the polynomial is contained in some interval I i. By refinement of a real zero is meant the process of replacing a given interval containing a real zero of the polynomial by successively smaller subintervals which still contain the zero. The process terminates when a subinterval of length less than a given arbitrary positive rational error bound is obtained.
In this paper a set of algorithms is presented and analyzed which employ congruence (modular, finite field) arithmetic to solve Problems (2) through (5) of the preceding paragraph. Congruence arithmetic has recently been used to produce several algebraic algorithms which are significantly faster, for sufficiently large and dense 109