Roots in finite fields

Square root

How do we compute a square root of an element in a finite field of characteristics of some prime $p$?

It holds:

$x^p = x$

$x^{p+1} = x^2$

Let’s say $p = 3$ mod $4$. Then it’s simple:

$x^{\frac{p+1}{4}} = x^{\frac{1}{2}}$

How about in an extended field $F_p(i)$ where $i^2 + 1 = 0$?

Let’s say we have an element $x_0 + x_1 i$.

If $x_1 = 0$, then let’s consider two options. If $x_0$ is a square, then we compute it as above for $F_p$. If it is not a square, we take $-x_0$ and compute a square root of this value in $F_p$. Let’s denote it by $y_0$. Then $(y_0 i)^2 = x_0$.

Let’s observe for $x_1 \neq 0$. We need $y_0 + i y_1$ such that:

$y_0^2 - y_1^2 = x_0$

$2 y_0 y_1 = x_1$

We can try to have $u + \frac{x_1}{2u} i$. We see that the second formula is satisfied this way. Further, it needs to hold:

$u^2 - \frac{x_1^2}{4u^2} = x_0$

$u^4 - x_0 u^2 - \frac{x_1^2}{4} = 0$

We solve the quadratic equation and get:

$u = \sqrt{\frac{x_0 \pm \sqrt{x_0^2 + x_1^2}}{2}}$

If $x_0^2 + x_1^2$ is not a square, we don’t have a solution.

Note that when the element is not a square, we need to take its negation, compute the square root of this negation and multiply it by $i$ (as above).

Fourth root

We have $x_0 + i x_1$ and we would like to get $y_0 + i y_1$ such that

$(y_0 + i y_1)^4 = x_0 + i x_1$

We have

$(y_0 + i y_1)^4 = y_0^4 - 6 y_0^2 y_1^2 + y_1^4 + i (4 y_0^3 y_1 - 4 y_0 y_1^3).$

We can use the fact that the norm is multiplicative, so:

$(y_0^2 + y_1^2)^4 = x_0^2 + x_1^2$

Let’s denote $n = y_0^2 + y_1^2$. We can compute $n$ as a fourth root in $F_p$.

We then have:

$x_0 = y_0^4 - 6 y_0^2 (n - y_0^2) + (n - y_0^2)^2$

$8 y_0^4 - 8 n y_0^2 + n^2 - x_0 = 0$

Let $u = y_0^2$. The discriminant of the equation above is:

$D = 64 n^2 - 32 (n^2 - x_0) = 32 (n^2 + x_0)$

And we have:

$u_{1,2} = \frac{8n \pm \sqrt D}{16}$

$= \frac{n \pm \sqrt{\frac{n^2 + x_0}{2}}}{2}$

So:

$y_0^2 = \frac{n \pm \sqrt{\frac{n^2 + x_0}{2}}}{2}$

To compute $y_0$ we need to compute two square roots in $F_p$. We can then compute $y_1$ out of

$x_1 = 4 y_1 y_0 (y_0^2 - (n - y_0^2))$

which requires one inversion.

Thus, we can compute the fourth root of an element in $F_p^2$ using one fourth root in $F_p$, two square roots in $F_p$ and one inversion. This is faster than repeated square roots, which would be four square roots in $F_p$ and two inversions.

Note that when $x_1 = 0$, we have:

$n^4 = (y_0^2 + y_1^2)^4 = x_0^2$

$n^2 = x_0$

So it’s either

$y_0^2 = \frac{n \pm \sqrt{\frac{n^2 + x_0}{2}}}{2} = \frac{n \pm \sqrt{x_0}}{2} = 0$

or

$y_0^2 = \frac{n \pm \sqrt{\frac{n^2 + x_0}{2}}}{2} = \frac{n \pm \sqrt{x_0}}{2} = n$

If $n$ is a square, we can take its square root:

$y_0 = \sqrt n$

If it is not a square, we have $y_0 = 0$ and we take

$y_1 = \sqrt[4]{x_0}$