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\}$$.

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

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