For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 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 \equiv 1$ mod $4$ there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in $\mathbb F_p$; it could have been anywhere between $\frac{p}{4}$ and $\frac{p}{2}$.

We show that for all $p \equiv 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 \equiv 1$ mod $4$, the degree of a polynomial computing square roots can be as small as $3p/8$.

We learnt that our upper bound for special p, Theorem 1.3, had been proved by Agou, Deliglése and Nicolas in 2003. Added some relevant references and did some small fixes.

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 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 \equiv 1$ mod $4$ there was previously no nontrivial bound known on the lowest degree of a polynomial computing square roots in $\mathbb F_p$; it could have been anywhere between $\frac{p}{4}$ and $\frac{p}{2}$.

We show that for all $p \equiv 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, we also show that for infinitely many $p \equiv 1$ mod $4$, the degree of a polynomial computing square roots can be $(\frac{1}{2} - \Omega(1))p$.