Squaring is an automorphism in GF(2^k). In more down to earth terms, to take a square root is just a linear map in terms of the basis over GF(2). The nicest basis to take, is a normal basis. In that case, taking a square root is just a rotation by 1 to the left. Victor On Mon, Jul 10, 2017 at 11:44 AM, Henry Baker <hbaker1@pipeline.com> wrote:

I did a quick Google search on discrete square roots, but most refs were for GF(p).

Is the complexity of taking a square root in GF(2^k) any less than taking an arbitrary discrete log?

How about the simple question of whether an element *has* a square root?

The reason I ask this question is due to the fact that:

(a+b)^2 (mod pp) = a^2 + 2ab + b^2 = a^2+b^2 (mod pp), where pp is the irreducible polynomial for the field GF(2^k), and a,b are representative polynomials whose degree is < deg(pp)=2^k.

So, (a*x^j+b)^2 = (a*x^j)^2 + b^2 = a^2*x^2j + b^2

So Karatsuba is even simpler/faster in these fields, hence, it might seem that finding such a square root might be easier than in some other fields.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun