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 \geq 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 (mod p)$ for some $x$ .

\begin{array}{r} \begin{matrix} (\frac{a}{p}) = {\begin{cases} 0, & p | a \\ 1, & a \in Q_{p} \\ - 1, & a \in {\overset{―}{Q}}_{p} \end{cases} \end{matrix} \end{array}

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 ${\overset{―}{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