We propose a new sparse GCD algorithm for multivariate polynomials over finite fields. Our algorithm uses a new type of substitution to recover the terms of the GCD in batches. We present a detailed complexity analysis and experimental results which show that our algorithm is faster than Zippel’s GCD algorithm and competitive with the Monagan-Hu GCD algorithm.

We propose two algorithms for sparse polynomial factorization over integers. The first one has good practical performance and is efficient for factoring polynomials with sparse irreducible factors. The second one is based on the effective Hilbert irreducibility theorem and has complexity polynomial in the sizes of the input and output, and the partial degree. At high level, the algorithms follow the standard approaches by reducing multi-variate polynomial factorization to univariate or bivariate polynomial factorization. Our main contributions are twofold. First, a new variable substitution is given, which reduces the multi-variate polynomial to a separated one, that is, the coefficients of its factors in a main variable are monomials. Second, “good” primes are selected such that the multi-variate factors can be recovered from the univariate or bivariate factors by direct division of the primes. As a consequence, the multivariate Hensel lifting in previous methods is avoided.

We propose a randomized algorithm for multiplication in the ring of non-commutative polynomials Κ [x1,…,xn]{#948;1,…,δn}, where δ i=xi∂over∂ xi, dedicated to sparse inputs. The complexity of our algorithm is polynomial in the input size and on an a priori sparsity bound for the output.

Consider the skew polynomial ring L[x; σ], where L is a field and σ is an automorphism of L of order r. We present two randomized algorithms for the multiplication of sparse skew polynomials in L[x;σ].

In this paper, we propose a new interpolation algorithm for a sparse multivariate polynomial represented by a straight-line program (SLP). Our algorithm is a Monte Carlo randomized algorithm and works over fields with large or zero characteristic. Let f be an n-variate polynomial given by a straight-line program, which has a degree bound D and a term bound T. For fields of large characteristic, the bit complexity of our algorithm is linear in n,T,łog D in the Soft-Oh sense. Since n,T,łog D are factors of the size of f, our algorithm is optimal in n,T and łog D in the Soft-Oh sense. For fields of characteristic 0, the arithmetic complexity of our algorithm is also linear in n,T,łog D in the Soft-Oh sense. But the arithmetic complexity does not account for coefficient growth and therefore might be a poor reflection of reality.