galois.jacobi_symbol

galois.jacobi_symbol(a: int, n: int) → int

Computes the Jacobi symbol $(\frac{a}{n})$ .

Parameters:¶

a: int¶: An integer.
n: int¶: An odd integer $n \geq 3$ .

Returns:¶

The Jacobi symbol $(\frac{a}{n})$ with value in ${0, 1, - 1}$ .

See also

legendre_symbol, kronecker_symbol

Notes¶

The Jacobi symbol extends the Legendre symbol for odd $n \geq 3$ . Unlike the Legendre symbol, $(\frac{a}{n}) = 1$ does not imply $a$ is a quadratic residue modulo $n$ . However, all $a \in Q_{n}$ have $(\frac{a}{n}) = 1$ .

References¶

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

Examples¶

The quadratic residues modulo 9 are $Q_{9} = {1, 4, 7}$ and these all satisfy $(\frac{a}{9}) = 1$ . The quadratic non-residues modulo 9 are ${\overset{―}{Q}}_{9} = {2, 3, 5, 6, 8}$ , but notice ${2, 5, 8}$ also satisfy $(\frac{a}{9}) = 1$ . The set of integers ${3, 6}$ not coprime to 9 satisfies $(\frac{a}{9}) = 0$ .

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

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