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
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    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