Beating brute force for systems of polynomial equations over finite fields

Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, Ryan Williams, Huacheng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

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)).

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages2190-2202
Number of pages13
ISBN (Electronic)9781611974782
DOIs
StatePublished - 2017
Externally publishedYes
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Country/TerritorySpain
CityBarcelona
Period1/16/171/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Beating brute force for systems of polynomial equations over finite fields'. Together they form a unique fingerprint.

Cite this