Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
3  
And that element $y$ will be simply $x^{2^{n-1}}$. ;) –  fkraiem Jul 3 at 20:04

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).

share|improve this answer
    
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 :( –  Arthur B Jul 3 at 20:16

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 of the 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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