The linear quantifier elimination algorithm for ordered fields in [15] is applicable to a wide range of examples involving even non-linear parameters. The Skolem sets of the original algorithm are generalized to elimination sets whose size is linear in the number of atomic formulas, whereas the size of Skolem sets is quadratic in this number. Elimination sets may contain non-standard terms which enter the computation symbolically. Many cases can be treated by special methods improving further the empirical computing times.

We design, analyze and measure several algorithms for finding the rational zeros of univariate polynomials with integral coefficients of any size. The quadratic Newton-Hensel type algorithm behaves best in theory and practice. It has a maximum computing time of $O(n^3 L(d)^2 )$, where n is the degree and d measures the coefficient size of the given squarefree polynomial using classical arithmetic. We extend the method to Gaussian rational numbers.