Abstract. We give new algorithms for converting between representations of polynomials with respect to certain kinds of bases, comprising the usual monomial basis and the falling factorial basis, for fast multiplication and Taylor shift in the falling factorial basis, and for computing the greatest factorial factorization. We analyze both the classical and the new algorithms in terms of arithmetic coefficient operations. For the special case of polynomials with integer coefficients, we present modular variants of these methods and give cost estimates in terms of word operations. Postscript

Abstract. We present new modular algorithms for the squarefree factorization of a primitive polynomial in Z[x] and for computing the rational part of the integral of a rational function in Q[x]. We analyze both algorithms with respect to classical and fast arithmetic and argue that the latter variants are---up to logarithmic factors---asymptotically optimal. Even for classical arithmetic, the integration algorithm is faster than previously known methods. Postscript

Abstract. We exhibit a class of proper hypergeometric expressions which lead to a key equation with coefficients of degree at most two and a unique solution of arbitrarily high degree in Gosper's algorithm from 1978 for indefinite hypergeometric summation. We investigate similar classes for the related problems of indefinite integration and q-hypergeometric summation. Postscript