6
$\begingroup$

Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?

$\endgroup$
11
$\begingroup$

Yes, there is an algorithm for efficiently computing square roots in $GF(2^n)$.

I don't know if this is the most efficient known, but the existence of an efficient algorithm can be shown by observing that squaring within $GF(2^n)$ is a bitwise linear operation, hence it is equivalent to taking the bit representation of the value, and multiplying it by an $n\times n$ matrix in $GF(2)$ to obtain the bit representation of the sequence. Hence, it can be inverted by computing the inverse matrix, and multiplying by that.

Also, you have tagged the question with the "quadratic-residuosity" tag; however the field $GF(2^n)$ has the special property that all elements are quadratic residues; that is, for any element $x$, there will exist a unique element $y$ with $y^2 = x$. Hence, in this field, the quadratic residuosity question is uninteresting.

$\endgroup$
  • 4
    $\begingroup$ And that element $y$ will be simply $x^{2^{n-1}}$. ;) $\endgroup$ – fkraiem Jul 3 '14 at 20:04
  • 1
    $\begingroup$ For anyone else wondering how the heck squaring can be linear, it's of course because $(x + y)^2 = x^2 + xy + yx + y^2 = x^2 + y^2$ in ${\rm GF}(2^n)$. The cross terms cancel in characteristic 2. Confused me for a moment. $\endgroup$ – Ilmari Karonen Apr 3 at 9:46
10
$\begingroup$

To complete poncho's answer, if you know some Galois theory. The map $\sigma: x\mapsto x^2$ from $\mathbf{F}_{2^n}$ to itself is simply the Frobenius automorphism (relative to $\mathbf{F}_2$). It generates the Galois group $\mathrm{Gal}\left(\mathbf{F}_{2^n}/\mathbf{F}_2\right)$, which is cyclic of order $n$, and so its inverse (which is, by definition, the square root mapping) is $\sigma^{-1} = \sigma^{n-1} : x\mapsto x^{2^{n-1}}$.

Of course, you can simply notice that $$\left(x^{2^{n-1}}\right)^2 = x^{2\cdot 2^{n-1}} = x^{2^n} = x$$ (because in finite fields, the whole machinery of Galois theory boils down to repeated applications of the Frobenius automorphism, since it generates the Galois group).

$\endgroup$
  • 1
    $\begingroup$ Ah the Frobenius automorphism was the motivation, I should have seen that. I haven't touched field theory in a decade and I'm rusty :( $\endgroup$ – Arthur B Jul 3 '14 at 20:16
  • $\begingroup$ @fkraiem - Let's assume that all you have is the polynomial $f(x)$ and you wish to apply this method to find its square root. A generator of some kind is needed, right? How would one determine what generator to use if all they had were $f(x)$? Will this work with any primitive generator with $degree >= n$? $\endgroup$ – Les Jul 30 '18 at 19:17
  • $\begingroup$ @Les What is "the polynomial $f(x)$"? $\endgroup$ – fkraiem Jul 30 '18 at 19:22
  • $\begingroup$ @Les And anyway, if you have a new question, please ask a new question. That's not what comments are for. $\endgroup$ – fkraiem Jul 30 '18 at 19:27
  • $\begingroup$ @fkraiem - Done. see here $\endgroup$ – Les Jul 30 '18 at 20:29
6
$\begingroup$

Nothing wrong with the other answers. I just want to point out that if you are using a normal basis representation of the field in question, then there is a very efficient way of calculating the square root. You recall that squaring an element is equivalent to cyclically rotating its coordinates w.r.t. the normal basis. Therefore to calculate the square root you rotate in the opposite direction.

The use of normal bases is one of the more efficient ways of doing arithmetic in $GF(2^n)$ with $n>100$ or so.

$\endgroup$
1
$\begingroup$

Yes, one common algorithm (faster than $\sqrt a = a^{2^{n-1}}$) is described in Field inversion and point halving revisited (Also revisited in Another Look at Square Roots and Traces (and Quadratic Equations) in Fields of Even Characteristic.)

Basically, if you want to compute $\sqrt a$ (modulo a binary polynomial $f(x)$), you split the odd coefficients of $a$ from the even coefficients, say $a_o$ and $a_e$ such that $a = a_e^2 + x \cdot a_o^2$ (note that squaring is just inserting zeroes between the coefficients).

For example, if $a = 1x^3 + 0x^2 + 0x + 1$, then $a = (0x + 1)^2 + x(1x + 0)^2$.

Then, if you consider the square root of both sides, you get $\sqrt a = a_e + \sqrt x \cdot a_o$. You can precompute $\sqrt x$ (depending on $f(x)$, it can be a very sparse polynomial); therefore, you can compute the square root by extracting even and odd coefficients, one multiplication by $f(x)$ (which is fast if $\sqrt x$ is sparse), one addition (xor) and one final modular reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.