Number theory symbols

boring_math.number_theory.legendre_symbol(a: int, p: int) → int

Legendre symbol

Calculate the Legendre Symbol (a/p) where p is an odd prime.

param a:

any integer

param p:

any prime p > 2, does not check that p is actually prime

returns:

the Legendre Symbol (a/p) ∈ {-1, 0, 1}

raises ValueError:

if abs(p) < 3

Note

See https://en.wikipedia.org/wiki/Legendre_symbol

boring_math.number_theory.jacobi_symbol(a: int, n: int) → int

Jacobi symbol

Calculate the Jacobi symbol (a/n) where n is a positive odd integer.

param a:

Any integer.

param n:

Any positive odd integer.

returns:

The Jacobi Symbol (a/n) ∈ {-1, 0, 1}.

raises ValueError:

If n is not a positive odd integer.

Note

See https://en.wikipedia.org/wiki/Jacobi_symbol