A. Akritas, An implementation of Vincent's theorem, Numerische Mathematik, vol.1, issue.1, pp.53-62, 1980.
DOI : 10.1007/BF01395988

S. Basu, R. Pollack, and M. Roy, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol.10, 2003.
DOI : 10.1007/978-3-662-05355-3
URL : https://hal.archives-ouvertes.fr/hal-01083587

G. E. Collins and R. Loos, Real zeros of polynomials, Computer Algebra: Symbolic and Algebraic Computation, pp.83-94, 1982.

J. H. Davenport, Cylindrical algebraic decomposition, School of Mathematical Sciences, 1988.

Z. Du, V. Sharma, and C. K. Yap, Amortized Bound for Root Isolation via Sturm Sequences, Int. Workshop on Symbolic Numeric Computing, pp.81-93, 2005.
DOI : 10.1007/978-3-7643-7984-1_8

A. Edelman and E. Kostlan, How may zeros of a random polynomial are real? Bulletin of, pp.1-37, 1995.

A. Eigenwillig, V. Sharma, and C. K. Yap, Almost tight recursion tree bounds for the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation , ISSAC '06, pp.71-78, 2006.
DOI : 10.1145/1145768.1145786

I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas, Real Algebraic Numbers: Complexity Analysis and Experimentation, Reliable Implementations of Real Number Algorithms: Theory and Practice, 2006.
DOI : 10.1007/978-3-540-85521-7_4

J. R. Johnson, Algorithms for Polynomial Real Root Isolation, 1991.
DOI : 10.1007/978-3-7091-9459-1_13

J. R. Johnson, W. Krandick, K. Lynch, D. Richardson, and A. Ruslanov, Highperformance implementations of the Descartes method, ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation, pp.154-161, 2006.

M. Kac, On the average number of real roots of a random algebraic equation, Bulletin of the American Mathematical Society, vol.49, issue.4, pp.314-320, 1943.
DOI : 10.1090/S0002-9904-1943-07912-8

W. Krandick, Isolierung reeller nullstellen von polynomen, Wissenschaftliches Rechnen, pp.105-154, 1995.

]. L. Kronecker, ¨ Uber den zahlbergriff, Crelle J. reine und angew. Mathematik, vol.101, pp.337-395, 1887.

J. M. Lane and R. F. Riesenfeld, Bounds on a polynomial, BIT, vol.24, issue.126, pp.112-117, 1981.
DOI : 10.1007/BF01934076

T. Lickteig and M. Roy, Sylvester???Habicht Sequences and Fast Cauchy Index Computation, Journal of Symbolic Computation, vol.31, issue.3, pp.315-341, 2001.
DOI : 10.1006/jsco.2000.0427

M. Mignotte, Mathematics for computer algebra, 1991.
DOI : 10.1007/978-1-4613-9171-5

M. Mignotte and D. Stefanescu, Polynomials: An algorithmic approach, 1999.

M. Mignotte, On the distance between the roots of a polynomial, Applicable Algebra in Engineering, Communication and Computing, vol.33, issue.145, pp.327-332, 1995.
DOI : 10.1007/BF01198012

B. Mourrain, F. Rouillier, and M. Roy, Bernstein's basis and real root isolation, Mathematical Sciences Research Institute Publications, pp.459-478, 2005.

B. Mourrain, M. Vrahatis, and J. C. Yakoubsohn, On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree, Journal of Complexity, vol.18, issue.2, 2002.
DOI : 10.1006/jcom.2001.0636

V. Y. Pan, Univariate polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation , ISSAC '01, pp.701-733, 2002.
DOI : 10.1145/384101.384136

J. R. Pinkert, An Exact Method for Finding the Roots of a Complex Polynomial, ACM Transactions on Mathematical Software, vol.2, issue.4, pp.351-363, 1976.
DOI : 10.1145/355705.355710

D. Reischert, Asymptotically fast computation of subresultants, Proceedings of the 1997 international symposium on Symbolic and algebraic computation , ISSAC '97, pp.233-240, 1997.
DOI : 10.1145/258726.258792

F. Rouillier and Z. Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, vol.162, issue.1, pp.33-50, 2004.
DOI : 10.1016/j.cam.2003.08.015

A. Schönhage, The fundamental theorem of algebra in terms of computational complexity, Manuscript. Univ. of Tübingen, 1982.

E. P. Tsigaridas and I. Z. Emiris, On the complexity of real root isolation using Continued Fractions. (submitted for journal publication), 2006.
URL : https://hal.archives-ouvertes.fr/inria-00116990

E. P. Tsigaridas and I. Z. Emiris, Univariate Polynomial Real Root Isolation: Continued Fractions Revisited, Proc. 14th European Symposium of Algorithms (ESA), pp.817-828, 2006.
DOI : 10.1007/11841036_72

J. Zur-gathen and J. Gerhard, Fast algorithms for Taylor shifts and certain difference equations, Proceedings of the 1997 international symposium on Symbolic and algebraic computation , ISSAC '97, pp.40-47, 1997.
DOI : 10.1145/258726.258745

J. Zur-gathen and J. Gerhard, Modern Computer Algebra, 2003.
DOI : 10.1017/CBO9781139856065

S. Herbert and . Wilf, A global bisection algorithm for computing the zeros of polynomials in the complex plane, J. ACM, vol.25, issue.3, pp.415-420, 1978.

C. K. Yap, Fundamental Problems of Algorithmic Algebra, 2000.

I. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399