Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications (Q4935306)

The sparse polynomial interpolation (SPI) problem is the following: Given: a field \(\mathbb K,\) a black box for evaluating a polynomial \(f\in \mathbb K[x_1,\ldots, x_n]\) as a polynomial function \(f:\mathbb K^n\rightarrow \mathbb K,\) an upper bound \(d\) for degree\((f),\) an upper bound \(t\) for the sparsity \(:=\) number \(k\) of distinct monomials \(M_i(x_1,\ldots, x_n)=x_1^{\alpha_{i1}}\ldots x_n^{\alpha_{in}}\) effectively occuring in \(f=\sum_{i=1}^k a_i M_i\) (i.e. \(a_i\in \mathbb K^*=\mathbb K\setminus \{0\}\)). Wanted: the exact sparsity \(k,\) the power strings \((\alpha_{i1}, \ldots, \alpha_{in})\), and the associated \(a_i.\) This problem has been treated by various authors whose results together with pondering their strengths and weaknesses are reviewed in the extensive introductory section. In this paper a 6-step algorithm for solving the SPI-problem for fields \(\mathbb K=GF(q),\) \(q=p^m,\) based on adaptions of an algorithm by \textit{M. Ben-Or} and \textit{P. Tiwari} [Proc. 20th ACM Symposium Theory of Computing, 301-309 (1988)] for the complex field is proposed and analysed. The algorithm given here improves upon a result given previously by \textit{D. Yu. Grigoriev, M. Karpinski}, and \textit{M. F. Singer} [SIAM J. Comput. 19, 1059-1063 (1990; Zbl 0711.68059)] and `is by far the most time efficient algorithm when the field is large'. Step 1. Let \(u_i(y)=((y+\gamma_1)^i, \ldots, (y+\gamma_n)^i)\in (GF(q)[y])^n,\) \(\gamma_i\in GF(q)\) distinct and let \(v_i(y)=f(u_i(y)).\) Step 2: Define the \(t\times t\) Hankel matrix \(V=(v_{i+j-2}(y))\) and let for \(l\leq t\) be \(V_l\) the left upper \(l\times l\) submatrix of \(V.\) Then the exact sparsity \(k=\max\{j:V_j \text{ is non singular}\}.\) Step 3: Determine the coefficients \(\lambda_i(y)\) of the polynomial \(\Lambda(z,y)=\prod_{i=1}^k (z-m_i(y))=\sum_{i=0}^k \lambda_i(y) z^i\) with \(m_i(y)=M_i(u_i(y))\) upon solving a certain linear system. Step 4: Factorize \(\Lambda(z,y)\) to determine all \(m_i(y).\) Step 5. Determine \(\alpha_{il}\) as the maximal \(\alpha\) such that \((y+\gamma_l)^{\alpha}\) divides \(m_i(y),\) \(l=1,\ldots,n.\) Step 6. Determine the \(a_i\) upon solving a certain linear system. The polynomials in Step 1, the (singularity of the) determinants in Step 2 and the determination of solutions known to be univariate polynomials of linear systems of matrices with univariate polynomial entries as occurring in Steps 3 and 6 are done by interpolation (substitution of sufficiently many field elements for recovering the polynomials for which degree bounds are known). For the factorization in Step 4 a factorization algorithm of \textit{J. von zur Gathen} and \textit{E. Kaltofen} [Math. Comput. 45, 251-261 (1985; Zbl 0596.12017)] is proposed; it is here that randomization enters. Theorem. The sparse polynomial interpolation problem can be solved by a Las Vegas randomized algorithm that performs \(O((td)^8((td)^5+\log(td)\log q) \log^4(td)\log^2 q)\) bit operations. It uses \(O((td)^6\log q)\) random bit choices and calls the input black box \(2t^2d-td+2t\) times; the probability that it announces failure is \(\leq 2^{-td}.\) Applications include a Monte Carlo Factorization, GCD, and Determinant Computation Section. Namely: Algorithm Factorization: Input: A polynomial \(f\in GF(q)[x_1,\ldots, x_n]\) of degree \(d\) in sparse representation, a rational number \(0<\delta <1.\) Output: Either `failure' or polynomials \(h_1, \ldots, h_r\in GF(q)[x_1, \ldots, x_n]\) in the sparse representation along with integers \(e_1, \ldots, e_r\) such that with probability \(\geq 1-\delta,\) \(f=\prod_{i=1}^r h_i^{e_i}\) with \(h_i\) irreducible. Algorithm GCD: Polynomials \(f_1,\ldots, f_r \in GF(q)[x_1, \ldots, x_n]\) with \(\deg(f_i)\leq d\) in sparse representation and a rational number \(0<\delta <1.\) Output: A polynomial \(g\in GF(q)[x_1,\ldots, x_n]\) in the sparse representation such that with probability \(\geq 1-\delta\) \(g\) is the GCD of \(f_1,\ldots, f_r.\) Algorithm: Sparse Determinant Computing Problem: Given as input a rational \(0<\delta<1\) and an \(r\times r\) matrix all of whose entries are specified as sparse representations of \(n\)-variate polynomials of degree at most \(d\) over a finite field \(GF(q)\) the output should be the sparse representation of \(g\in GF(q)[x_1,\ldots, x_n]\) such that with probability \(\geq 1-\delta,\) \(g\) is the symbolic determinant.