  We consider two kinds of problems: the computation of polynomial and rational
solutions of linear recurrences with coefficients that are polynomials with
integer coefficients; indefinite and definite summation of sequences that are
hypergeometric over the rational numbers. The algorithms for these tasks all
involve as an intermediate quantity an integer $N$ (dispersion or root of an
indicial polynomial) that is potentially exponential in the bit size of their
input. Previous algorithms have a bit complexity that is at least quadratic in
$N$. We revisit them and propose variants that exploit the structure of
solutions and avoid expanding polynomials of degree $N$. We give two
algorithms: a probabilistic one that detects the existence or absence of
nonzero polynomial and rational solutions in $O(\sqrt{N}\log^{2}N)$ bit
operations; a deterministic one that computes a compact representation of the
solution in $O(N\log^{3}N)$ bit operations. Similar speed-ups are obtained in
indefinite and definite hypergeometric summation. We describe the results of an
implementation.
