A thought on deterministic square root extraction in finite fields had crossed my mind. In a recent paper by Tsz Wo Sze, “On taking square roots without quadratic nonresidues over finite fields”, Mathematics of Computation, volume 80, number 275, essentially, an algorithm is given that works in time polynomial in , where the field we are working in is .
The only other deterministic square root algorithm is Schoof’s (that I’m aware of). As Tsz Wo Sze comments, if we could keep taking square roots: , we would end up with a non-residue, which can be used in the Tonelli-Shanks algorithm. So, I was thinking, why not try the obvious generalisation of Schoof’s algorithm using the hyperelliptic curves :
where , so that the Frobenius endomorphism can be expressed in , and some algebra gives us an explicit . We see that if is bounded by a polynomial function in , we should have a polynomial time deterministic algorithm for square roots in . I don’t know, maybe there’s some kind of catch.