Modular Sturm Sequences?

David P. Jacobs
Dept. of Computer Science, Clemson University
Clemson, SC 29634{1906 USA
[email protected]
Vilmar Trevisan
UFRGS{Instituto de Matem?atica
91509{900 Porto Alegre, RS, Brasil
[email protected]
Kenneth Weber
Dept. of Computer Science, Mount Union College
1972 Clark Avenue
Alliance, OH 44601{3993 USA
[email protected]

August 24, 1996

Abstract
We describe a modular algorithm, based on Sturm's Theorem, for computing the number of distinct real roots of a polynomial f(x) 2 Q[x], in an interval [a; b], where a and b are rationals.
key words: Chinese remainder theorem, Sturm's theorem, polynomial.

1 Introduction

Isolating roots of a complex polynomial is a problem of recognized importance in many areas of applied sciences and it has been studied by many mathematicians. Tools that are used to solve the isolation problem include the principle of the argument and ?This work was partially supported by CNPq while the first and third author were visiting UFRGS.