Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

DOI10.1006/JAGM.1999.1045MaRDI QIDQ4935306zbMATH OpenOpenAlexFDO

Publication date 19 March 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1999.1045

bit operations complexity determinant factorization finite field greatest common divisor interpolation Las Vegas algorithm Monte Carlo algorithm multivariate polynomial parallel algorithm randomized algorithm sparse polynomial interpolation

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Review text

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.

Recommendations

Cited in

(31)

This page was built for publication: Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4935306)