Solvability of Systems of Polynomial Equations over Finite Fields
summary
Claim: for any fixed number of variables N there is a deterministic algorithm that decides solvability over F_p in time polynomial in input size but with a current exponent roughly D^{2^N} (suspected reducible to D^N); randomized methods give polynomial-time root finding and derandomized partial factorization. Key tools are GCD with X^p−X via repeated squaring, residue splitting by random shifts and resultants to reduce bivariate cases to univariate, use of Weil bounds and absolute irreducibility, and factoring/Hensel-lifting ideas (Berlekamp, Cantor–Zassenhaus, Kaltofen/Gao).
AI-written summary · about