2026-08-07T05:25:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20421 2024-07-15T12:26:46Z ddc:004 open_access

On the Degree of Polynomials Computing Square Roots Mod p Kedlaya, Kiran S. Kopparty, Swastik Algebraic Computation Polynomials Computing Square roots Reed-Solomon Codes For an odd prime p, we say f(X) ∈ F_p[X] computes square roots in F_p if, for all nonzero perfect squares a ∈ F_p, we have f(a)² = a. When p ≡ 3 mod 4, it is well known that f(X) = X^{(p+1)/4} computes square roots. This degree is surprisingly low (and in fact lowest possible), since we have specified (p-1)/2 evaluations (up to sign) of the polynomial f(X). On the other hand, for p ≡ 1 mod 4 there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in F_p. We show that for all p ≡ 1 mod 4, the degree of a polynomial computing square roots has degree at least p/3. Our main new ingredient is a general lemma which may be of independent interest: powers of a low degree polynomial cannot have too many consecutive zero coefficients. The proof method also yields a robust version: any polynomial that computes square roots for 99% of the squares also has degree almost p/3. In the other direction, Agou, Deliglése, and Nicolas [Agou et al., 2003] showed that for infinitely many p ≡ 1 mod 4, the degree of a polynomial computing square roots can be as small as 3p/8. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kiran S. Kedlaya and Swastik Kopparty 2024 Is Part Of LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2024.25 urn:nbn:de:0030-drops-204219 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.25 eng https://creativecommons.org/licenses/by/4.0/legalcode