Determines if the elements of \(x\) are quadratic residues in the finite field.

Returns¶

A boolean array indicating if each element in \(x\) is a quadratic residue. The return value is a single boolean if the input array \(x\) is a scalar.

Notes¶

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.

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

References¶

• Section 3.5.1 from https://cacr.uwaterloo.ca/hac/about/chap3.pdf.

Examples¶

Since \(\mathrm{GF}(2^3)\) has characteristic 2, every element has a square root.

In [1]: GF = galois.GF(2**3, display="poly")

In [2]: x = GF.elements; x
Out[2]: 
GF([          0,           1,           α,       α + 1,         α^2,
        α^2 + 1,     α^2 + α, α^2 + α + 1], order=2^3)

In [3]: x.is_quadratic_residue()
Out[3]: array([ True,  True,  True,  True,  True,  True,  True,  True])

In \(\mathrm{GF}(11)\), the characteristic is greater than 2 so only half of the elements have square roots.

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

In [5]: x = GF.elements; x
Out[5]: GF([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10], order=11)

In [6]: x.is_quadratic_residue()
Out[6]: 
array([ True,  True, False,  True,  True,  True, False, False, False,
        True, False])