notes
- November 30, 2023

# 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

It holds:

Let’s say

Then it’s simple:How about in an extended field

whereLet’s say we have an element

If

then let’s consider two options. If is a square, then we compute it as above for If it is not a square, we take and compute a square root of this value in Let’s denote it by ThenLet’s observe for

We need such that:We can try to have

We see that the second formula is satisfied this way. Further, it needs to hold:We solve the quadratic equation and get:

If

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

(as above).## Fourth root

We have

and we would like to get such thatWe have

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

Let’s denote

We can compute as a fourth root inWe then have:

Let

The discriminant of the equation above is:And we have:

So:

To compute

we need to compute two square roots in We can then compute out ofThus, we can compute the fourth root of an element in

using one fourth root in two square roots in and one inversion. This is faster than repeated square roots, which would be four square roots in and two inversions.Note that when

we have:So it’s either

If

is a square, we can take its square root: