Deterministic Square Rooting

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 \sum_{q|p-1}q, where the field we are working in is \mathbb{F}_p.

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: -1, \sqrt{-1}, \sqrt[4]{-1}, \dots, 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 C_s:

y^2=x^{2^s}+1

where 2^s || p-1, so that the Frobenius endomorphism can be expressed in End(C_s)\cong \mathbb{Z}[\zeta_{2^s}], and some algebra gives us an explicit \sqrt[2^s]{-1}. We see that if s is bounded by a polynomial function in \log \log{p}, we should have a polynomial time deterministic algorithm for square roots in \mathbb{F}_p. I don’t know, maybe there’s some kind of catch.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s