Computing square roots in a finite field¶

This notebook gives some example code which shows how to compute square roots in a finite field. It may be useful when solving questions related to what points are on a given Edwards curve.

In [1]:
# Here, we use a finite field of size 17
p = 17
Fp = GF(p)
In [2]:
# We compute the square roots and print them
for i in range(0, Fp.cardinality()):
    print(str(i).rjust(len(str(Fp.cardinality()))), "has square roots", Fp(i).sqrt(extend=False, all=True))
 0 has square roots [0]
 1 has square roots [1, 16]
 2 has square roots [6, 11]
 3 has square roots []
 4 has square roots [2, 15]
 5 has square roots []
 6 has square roots []
 7 has square roots []
 8 has square roots [5, 12]
 9 has square roots [3, 14]
10 has square roots []
11 has square roots []
12 has square roots []
13 has square roots [8, 9]
14 has square roots []
15 has square roots [7, 10]
16 has square roots [4, 13]