In a earlier post I introduce the Legendre symbolwhere a is a positive integer and p is prime.
It is defined to be 0 if a is a multiple of p, 1 if a has a square root mod p, and -1 otherwise.
The Jacobi symbol is a generalization of the Legendre symbol and uses the same notation.
It relaxes the requirement that p be prime and only requires that p is odd.
If m has prime factors pi with exponents ei, then the Jacobi symbol is defined byNote that the symbol on the left is a Jacobi symbol while the symbols on the right are Legendre symbols.
The Legendre and Jacobi symbols are not fractions, but they act in some ways like fractions, and so the notation is suggestive.
They come up in applications of number theory, so it’s useful to be able to compute them.
Algorithm for computing Jacobi symbolsSince the Legendre symbol is a special case of the Jacobi symbol, we only need an algorithm for computing the latter.
In the earlier post mentioned above, I outline an algorithm for computing Legendre symbols.
The code below is more explicit, and more general.
It’s Python code, but it doesn’t depend on any libraries or special features of Python, so it could easily be translated to another language.
The algorithm is taken from Algorithmic Number Theory by Back and Shallit.
def jacobi(a, n): assert(n > a > 0 and n%2 == 1) t = 1 while a != 0: while a % 2 == 0: a /= 2 r = n % 8 if r == 3 or r == 5: t = -t a, n = n, a if a % 4 == n % 4 == 3: t = -t a %= n if n == 1: return t else: return 0 Testing the Python codeTo test the code we randomly generate positive integers a and odd integers n greater than a.
We compare our self-contained Jacobi symbol function to the one in SymPy.
N = 1000 for _ in range(100): a = randrange(1, N) n = randrange(a+1, 2*N) if n%2 == 0: n += 1 j1 = jacobi_symbol(a, n) j2 = jacobi(a, n) if j1 != j2: print(a, n, j1, j2) This prints nothing, suggesting that we coded the algorithm correctly.
Related postsQuadratic reciprocityBlum Blum Shub cryptographic RNGGraphs and square roots modulo a prime.. More details