A note on square roots in finite fields
Eric Bach · IEEE Transactions on Information Theory · 1990
A simple method showing the quadratic character in a finite field of odd order q can be computed in O(log/sup 2/ q) steps is presented. It is also shown how sequences generated deterministically from a random seed can be used reliably in a recent randomized algorithm of R. Peralta (1986) for computing square roots in finite fields.>