On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields (Q1178687)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields |
scientific article |
Statements
On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields (English)
0 references
26 June 1992
0 references
The method of sparse representation, i.e. representing a polynomial by a list of records containing a nonzero coefficient and the corresponding exponent is proved to be very successful. In this paper the authors consider these methods and problems for \(k\)-sparse multivariate polynomials over finite field \(K\) with essentially no restriction on the degree of the polynomials. Several strategies are known already for polynomials over fields of characteristic zero. The equally important, but more complicated case of a finite field \(K\) of small characteristic is studied in this paper. The result is that the time complexity of such strategies depends on the degree of the extension fields of \(K\) from which the arguments are to be chosen.
0 references
zero-testing
0 references
interpolation
0 references
method of sparse representation
0 references
\(k\)-sparse multivariate polynomials
0 references
finite field
0 references
time complexity
0 references
0 references