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 \ge 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 \ge 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 \(\overline{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