class property galois.FieldArray.quadratic_residues : FieldArray

All quadratic residues in the finite field.

An element \(x\) in \(\mathrm{GF}(p^m)\) is a quadratic residue if there exists a \(y\) such that \(y^2 = x\) in the field.

See also

is_quadratic_residue

Examples

In fields with characteristic 2, every element is a quadratic residue.

In [1]: GF = galois.GF(2**4)

In [2]: x = GF.quadratic_residues; x
Out[2]: 
GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
   order=2^4)

In [3]: r = np.sqrt(x); r
Out[3]: 
GF([ 0,  1,  5,  4,  2,  3,  7,  6, 10, 11, 15, 14,  8,  9, 13, 12],
   order=2^4)

In [4]: np.array_equal(r ** 2, x)
Out[4]: True

In [5]: np.array_equal((-r) ** 2, x)
Out[5]: True

In fields with characteristic greater than 2,exactly half of the nonzero elements are quadratic residues (and they have two unique square roots).

In [6]: GF = galois.GF(11)

In [7]: x = GF.quadratic_residues; x
Out[7]: GF([0, 1, 3, 4, 5, 9], order=11)

In [8]: r = np.sqrt(x); r
Out[8]: GF([0, 1, 5, 2, 4, 3], order=11)

In [9]: np.array_equal(r ** 2, x)
Out[9]: True

In [10]: np.array_equal((-r) ** 2, x)
Out[10]: True
Last update: Jul 24, 2022