TY - GEN

T1 - Beating brute force for systems of polynomial equations over finite fields

AU - Lokshtanov, Daniel

AU - Paturi, Ramamohan

AU - Tamaki, Suguru

AU - Williams, Ryan

AU - Yu, Huacheng

N1 - Funding Information:
University of California, San Diego paturi@cs.ucsd.edu. This research is supported by NSF grant CCF-1213151 from the Division of Computing and Communication Foundations. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. §Kyoto University tamak@kuis.kyoto-u.ac.jp. Supported in part by MEXT KAKENHI (24106003); JSPS KAKENHI (25240002, 26330011); the John Mung Advanced Program of Kyoto University. Part of the work performed while the author was at Department of Computer Science and Engineering, University of California, San Diego. ¶Stanford University. rrw@cs.stanford.edu, yuhch123@gmail.com. Supported by an Alfred P. Sloan Fellowship and NSF grants CCF-1212372 and CCF-1552651 (CAREER). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the NSF.
Publisher Copyright:
Copyright © by SIAM.

PY - 2017

Y1 - 2017

N2 - We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≥ 2 and finite field Fq where q = pd for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O(qn) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time qn+o(n) · qn+O(k) time if q ≤ 24ekd, and qn+O(n) · ( logq dek ) -dn otherwise, where e = 2.718. . . is Napier's constant, and a deterministic algorithm for counting solutions with running time qn+O(n) · qn+O(kq6/7d ). For the important special case of quadratic equations in F2, our randomized algorithm has running time O(20.8765n). For systems over F2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a circuit, i.e., a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2n-δn for δ= 1/O(log(s/n)) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O(log(s/n)).

AB - We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≥ 2 and finite field Fq where q = pd for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O(qn) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time qn+o(n) · qn+O(k) time if q ≤ 24ekd, and qn+O(n) · ( logq dek ) -dn otherwise, where e = 2.718. . . is Napier's constant, and a deterministic algorithm for counting solutions with running time qn+O(n) · qn+O(kq6/7d ). For the important special case of quadratic equations in F2, our randomized algorithm has running time O(20.8765n). For systems over F2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a circuit, i.e., a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2n-δn for δ= 1/O(log(s/n)) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O(log(s/n)).

UR - http://www.scopus.com/inward/record.url?scp=85016209017&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016209017&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.143

DO - 10.1137/1.9781611974782.143

M3 - Conference contribution

AN - SCOPUS:85016209017

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2190

EP - 2202

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -