galois.legendre_symbol¶

galois.legendre_symbol(a: int, p: int) → int¶

Computes the Legendre symbol \((\frac{a}{p})\).

Parameters

a: int¶

An integer.

p: int¶

An odd prime \(p \ge 3\).

Returns

The Legendre symbol \((\frac{a}{p})\) with value in \(\{0, 1, -1\}\).

See also

jacobi_symbol, kronecker_symbol

Notes

The Legendre symbol is useful for determining if \(a\) is a quadratic residue modulo \(p\), namely \(a \in Q_p\). A quadratic residue \(a\) modulo \(p\) satisfies \(x^2 \equiv a\ (\textrm{mod}\ p)\) for some \(x\).

\[ \begin{align}\begin{aligned}\bigg(\frac{a}{p}\bigg) = \begin{cases} 0, & p\ |\ a\\ 1, & a \in Q_p\\ -1, & a \in \overline{Q}_p \end{cases}\end{aligned}\end{align} \]

References

• Algorithm 2.149 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf

Examples

The quadratic residues modulo \(7\) are \(Q_7 = \{1, 2, 4\}\). The quadratic non-residues modulo \(7\) are \(\overline{Q}_7 = \{3, 5, 6\}\).

In [1]: [pow(x, 2, 7) for x in range(7)]
Out[1]: [0, 1, 4, 2, 2, 4, 1]

In [2]: for a in range(7):
   ...:     print(f"({a} / 7) = {galois.legendre_symbol(a, 7)}")
   ...: 
(0 / 7) = 0
(1 / 7) = 1
(2 / 7) = 1
(3 / 7) = -1
(4 / 7) = 1
(5 / 7) = -1
(6 / 7) = -1