The Structure and Degrees of Polynomials Computing Square Roots $\mathrm{mod}p$

Foivos Chnaras, Noah Kupinsky

For an odd prime $p$, we say a polynomial $f\in {\mathbb{F}}_p[X]$ computes square roots if $f(a{)}^2=a$ for all nonzero, perfect squares $a\in {\mathbb{F}}_p$. When $p\equiv 3\mathrm{mod}4$, it…