Sparse polynomial interpolation: faster strategies over finite fields

Giorgi P., Grenet B., Perret du Cray A., Roche D.S.

Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing the exact quotient of two given polynomials. These methods are efficient in terms of the bit-length of the sparse representation, that is, the number of nonzero terms, the size of coefficients, the number of variables, and the logarithm of the degree. At the core of our results is a new Monte Carlo randomized algorithm to recover a polynomial f(x) with integer coefficients given a way to evaluate f(θ) mod m for any chosen integers θ and m. This algorithm has nearly-optimal bit complexity, meaning that the total bit-length of the probes, as well as the computational running time, is softly linear (ignoring logarithmic factors) in the bit-length of the resulting sparse polynomial. To our knowledge, this is the first sparse interpolation algorithm with soft-linear bit complexity in the total output size. For polynomials with integer coefficients, the best previously known results have at least a cubic dependency on the bit-length of the exponents.

Harvey D., van der Hoeven J.

Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than  \( n \) over a finite field \( \mathbb {F}_q \) with  \( q \) elements can be multiplied in time \( O (n \log q \log (n \log q)) \) , uniformly in \( q \) . Under the same hypothesis, we show how to multiply two \( n \) -bit integers in time \( O (n \log n) \) ; this algorithm is somewhat simpler than the unconditional algorithm from the companion paper [ 22 ]. Our results hold in the Turing machine model with a finite number of tapes.

Huang Q., Gao X.

In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let f be an n -variate polynomial given by a straight-line program, which has a total degree bound D and a term bound T . Our deterministic algorithm is quadratic in n , T and cubic in log ⁡ D in the Soft-Oh sense, which has better complexities than existing deterministic interpolation algorithms in most cases. Our Monte Carlo interpolation algorithms have better complexities than existing Monte Carlo interpolation algorithms and are the first algorithms whose complexities are linear in nT and polynomial in log ⁡ D in the Soft-Oh sense.

Giorgi P., Grenet B., Cray A.P.

We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of the input and the output. Our algorithm works for any field of characteristic zero or larger than the degree. We mainly rely on sparse interpolation and on a new algorithm for verifying a sparse product that has also a quasi-linear time complexity. Using Kronecker substitution techniques we extend our result to the multivariate case.

Huang Q.

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.

Roche D.S.

Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.

Sedunova A.

van der Hoeven J., Larrieu R.

Let Fq be the finite field with q elements and let ω be a primitive n-th root of unity in an extension field Fqd of Fq. Given a polynomial P ∈ Fq [x] of degree less than n, we will show that its discrete Fourier transform (P (ω0), ..., P (ωn - 1)) ∈ Fqdn can be computed essentially d times faster than the discrete Fourier transform of a polynomial Q ∈ Fqd [x] of degree less than n, in many cases. This result is achieved by exploiting the symmetries provided by the Frobenius automorphism of Fqd over Fq.

Harvey D., Hoeven J.V., Lecerf G.

Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let M p ( n ) denote the bit complexity of multiplying two polynomials in F p [ X ] of degree less than n . For n large compared to p , we establish the bound M p ( n ) = O ( n log n 8 log* n log p ), where log * n = min{ k ϵ N: log … k × … log n ≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M p ( n ) = O ( n log n log log n log p ), which essentially goes back to the 1970s.

Hu J., Monagan M.

We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. We have implemented our algorithm in Cilk C. We compare it with Maple and Magma's implementations of Zippel's GCD algorithm.

Arnold A., Giesbrecht M., Roche D.S.

Given a straight-line program whose output is a polynomial function of the inputs, we present a new algorithm to compute a concise representation of that unknown function. Our algorithm can handle any case where the unknown function is a multivariate polynomial, with coefficients in an arbitrary finite field, and with a reasonable number of nonzero terms but possibly very large degree. It is competitive with previously known sparse interpolation algorithms that work over an arbitrary finite field, and provides an improvement when there are a large number of variables.

Grenet B., van der Hoeven J., Lecerf G.

We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field $$\mathbb {F}_q$$ . Our algorithms were designed to be particularly efficient in the case when the cardinality $$q - 1$$ of the multiplicative group of $$\mathbb {F}_q$$ is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders.

Grenet B., van der Hoeven J., Lecerf G.

Consider a finite field Fq whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over Fq, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and slightly improve existing algorithms and then present new randomized ones based on the Graeffe transform. We report on our implementation in the MATHEMAGIX computer algebra system, confirming that our ideas gain by a factor ten at least in practice, for sufficiently large inputs.

van der Hoeven J., Lecerf G.

We present a few techniques which allow to make better use of hardware integer arithmetic when implementing algorithms for sparse polynomial interpolation.

Arnold A., Giesbrecht M., Roche D.S.

We present a new Monte Carlo algorithm for the interpolation of a straight-line program as a sparse polynomial f over an arbitrary finite field of size q. We assume a priori bounds D and T are given on the degree and number of terms of f. The approach presented in this paper is a hybrid of the diversified and recursive interpolation algorithms, the two previous fastest known probabilistic methods for this problem. By making effective use of the information contained in the coefficients themselves, this new algorithm improves on the bit complexity of previous methods by a "soft-Oh" factor of T, log D, or log q.

Demin A., van der Hoeven J.

van der Hoeven J., Lecerf G.