Deterministic test finds shifts between sparse high-degree polynomials
Deterministic Shift Equivalence Testing for Sparse Polynomials
Data Structures and AlgorithmsComputational Complexity
Summary
The paper addresses the challenge of checking whether two complicated mathematical expressions called sparse polynomials can be matched by shifting their input variables. The authors provide a reliable method that can find this shift exactly when it exists, and they prove this method works efficiently even when the polynomials have many variables and very high degrees. This solves an open problem from earlier work that could not handle sparse polynomials well. Their method works over rational numbers and similar mathematical settings.
What this means in practice
- •For computer algebra developers: Implement reliable algorithms that check polynomial equivalences with shifts for symbolic computation software, improving correctness and efficiency.
- •For cryptography engineers: Enhance tools verifying equivalences in polynomial-based cryptographic schemes where shifts of sparse polynomials can arise, aiding security analysis.
A theory result. No direct application yet.
Authors
Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal
Abstract
We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a vector $\mathbf{a}\in\mathbb{Q}^n$ such that $f(\mathbf{x}+\mathbf{a})\equiv g(\mathbf{x})$. Furthermore, one needs to output such a vector if it exists. Dvir, Oliveira, and Shpilka (ICALP 2014) studied shift equivalence for low-degree arithmetic circuits. Their framew ork does not apply directly to sparse polynomials, which are not closed under shifts, and they left open whether shift equivalence of sparse polynomials admits an efficient deterministic algorithm. We answer this question positively over $\mathbb{Q}$. If the input coefficients have bit-size at most $τ$, we sh ow that a rational shift of polynomial bit-size exists whenever the polynomials are shift equivalent. Moreover, our alg orithm outputs such a shift and has a running time of $\operatorname{poly}(n,s,t,τ,\log d)$ in the bit model. The ar ithmetic and structural parts of our result also hold over any field of characteristic zero or characteristic larger th an $d$.