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 ... more >>>