The aim of this paper is to present a solution for two important problems in computer algebra: sparse polynomial zero-testing and interpolation over a finite field. These problems can be formulated in the following terms. Given a k -sparse multivariate polynomial over a finite field by means of a black box (a straight-line program evaluating this polynomial), the zero-testing problem is to determine a finite set A such that, if the value of F is 0 for every element in A, then F is the zero-polynomial. The interpolation problem asks us to determine a finite set B such that it is possible to recover the coefficients of F knowing the values of F over the elements of B. Both sets depend on k, the number of elements in the field, and the number of variables.
The authors’ solution for the zero-testing problem uses a set of points in G F ( q n ) n whose coordinates are powers (with exponent bounded by k q n - 1 ) of a primitive element of G F ( q n ) as the test set for a k -sparse multivariate polynomial in G F ( q )[ X 0 ,..., X n - 1 ]. They use this result to derive the main result of Section 2, which states that, given fixed k and n, it is possible to construct testing sets in G F ( q m ) for any given m with cardinality O ( k log ( n&slash;m ) ).
Section 3 is devoted to deriving lower bounds for the cardinality of a testing set in G F ( q m ) for fixed k and n. The bound is for the case in which no extensions of the ground field are allowed. An optimal algorithm is proposed for the particular case of G F ( 2 ).
Finally, using the results obtained in Section 2, Section 4 provides an algorithm to reconstruct a k -sparse polynomial F ∈ G F ( q ) [ X 0 ,..., X n - 1 ] with deg X i ( F ) < q for all i. This algorithm uses only 1 + 2 k - ⌊ ( 2 k - 1 ) &slash; q ⌋ evaluations over G F ( q n ).
The paper is well written and clear. The authors provide detailed proofs of their results and an extended list of references.
-sparse multivariate polynomials over finite fields
