  We present a new Monte Carlo algorithm for the interpolation of a
straight-line program as a sparse polynomial $f$ over an arbitrary finite field
of size $q$. We assume a priori bounds $D$ and $T$ are given on the degree and
number of terms of $f$. The approach presented in this paper is a hybrid of the
diversified and recursive interpolation algorithms, the two previous fastest
known probabilistic methods for this problem. By making effective use of the
information contained in the coefficients themselves, this new algorithm
improves on the bit complexity of previous methods by a "soft-Oh" factor of
$T$, $\log D$, or $\log q$.
