2023/11/18 by Kiran S. Kedlaya, Swastik Kopparty, Kedlaya, Kiran +1 · 1 citation
Computer Science · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2311.10956
openalex publication_date 2023/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For an odd prime p, we say f(X) ∈ \mathbb Fp[X] computes square roots in \mathbb Fp if, for all nonzero perfect squares a ∈ \mathbb Fp, we have f(a)2 = 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 \mathbb Fp; it could have been anywhere between (p)/(4) and (p)/(2). 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, a result of Agou, Deliglése, and Nicolas (Designs, Codes, and Cryptography, 2003) shows that for infinitely many p ≡ 1 \mod 4, the degree of a polynomial computing square roots can be as small as 3p/8.