## Modular algorithms for polynomial basis conversion and greatest factorial factorization

*Jürgen Gerhard*

**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

## Fast modular algorithms for squarefree factorization and Hermite integration

*Jürgen Gerhard*

**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

## High degree solutions of low degree equations

*Jürgen Gerhard*

**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

Author: Jürgen Gerhard, last change: 8 March 2001