Computing Legendre and Jacobi symbols
In a earlier post I introduce the Legendre symbol
where 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 by
Note 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 Bach and Shallit. Its execution time is O( (log a)(log n) ).
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 0Testing the Python code
To 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 posts