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

where

Let’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
Then

Let’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 that

We have

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

Let’s denote

We can compute
as a fourth root in

We 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 of
which requires one inversion.

Thus, 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

or

If

is a square, we can take its square root:
If it is not a square, we have
and we take

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter