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:


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.

Large 3-Ranks of Class Groups

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 E is an elliptic curve given by the Weierstrass equation

y^2 = x^3+a_2x^2+a_4x+a_6

a_6<0, and P=(x_0,y_0) \in E(\mathbb{Q}) a point that satisfies a small technical condition called primitive, then we send P to
[(x_0,y_0-\sqrt{a_6})] \in Cl(\mathbb{Q}(\sqrt{a_6}))
The primitive points form a subgroup of finite index in E(\mathbb{Q}).

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 n \in \mathbb{Z}, that is negative enough, we can shift the elliptic curve to get a new Weierstrass equation

y^2 = (x+n)^3+a_2(x+n)^2+a_4(x+n)+a_6 = x^3+\ldots+(n^3+a_2n^2+a_4n+a_6)

So the new a_6 is the polynomial evaluated at n. If this value is a square times the old value, we should get another map from E to the same class group. This is equivalent to n being the x coordinate of a point on the a_6-quadratic twist of E. Note that this quadratic twist always has the point (0,1). Multiples of this point give candidate values for n, 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.