  We consider the problem of interpolating a sparse multivariate polynomial
over a finite field, represented with a black box. Building on the algorithm of
Ben-Or and Tiwari for interpolating polynomials over rings with characteristic
zero, we develop a new Monte Carlo algorithm over the finite field by doing
additional probes. To interpolate a polynomial $f\in F_q[x_1,\dots,x_n]$ with a
partial degree bound $D$ and a term bound $T$, our new algorithm costs
$O^\thicksim(nT\log ^2q+nT\sqrt{D}\log q)$ bit operations and uses $2(n+1)T$
probes to the black box. If $q\geq O(nT^2D)$, it has constant success rate to
return the correct polynomial. Compared with previous algorithms over general
finite field, our algorithm has better complexity in the parameters $n,T,D$ and
is the first one to achieve the complexity of fractional power about $D$, while
keeping linear in $n,T$. A key technique is a randomization which makes all
coefficients of the unknown polynomial distinguishable, producing a diverse
polynomial. This approach, called diversification, was proposed by Giesbrecht
and Roche in 2011. Our algorithm interpolates each variable independently using
$O(T)$ probes, and then uses the diversification to correlate terms in
different images. At last, we get the exponents by solving the discrete
logarithms and obtain coefficients by solving a linear system. We have
implemented our algorithm in Maple. Experimental results shows that our
algorithm can applied to sparse polynomials with large degree. We also analyze
the success rate of the algorithm.
