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.
Here’s an idea I once had for generating class groups of imaginary quadratic fields with large 3-ranked class group, maybe you can make something of it:
In Rankin Soleng’s paper “Homomorphisms From the Group of Rational Points On Elliptic Curves to Class Groups of Quadratic Number Fields”, J. Number Theory Volume 46, Issue 2, Feburary 1994, homomorphisms from a subgroup of rational points on an elliptic curve to certain class groups are defined.
Say is an elliptic curve given by the Weierstrass equation
, and a point that satisfies a small technical condition called primitive, then we send to
The primitive points form a subgroup of finite index in .
Soleng uses these homomorphisms to generate families of imaginary quadratic number fields with non-trivial 3-ranked class group, just by using elliptic curves with with non-trivial 3-torsion.
My idea is then to try to build more than one homomorphism into the same class group. For any , that is negative enough, we can shift the elliptic curve to get a new Weierstrass equation
So the new is the polynomial evaluated at . If this value is a square times the old value, we should get another map from to the same class group. This is equivalent to being the coordinate of a point on the -quadratic twist of . Note that this quadratic twist always has the point . Multiples of this point give candidate values for , of course only finitely many integral.
If we have an elliptic curve, with non-trivial 3-torsion, and with many of these different homomorphisms into the same class group, we should expect the class group to have a large 3-rank.
I tried for a few days to get this to work and gave up after a while.