Legendre and Jacobi Symbols

Jacobi Symbol

The Jacobi symbol is used to simplify computations involving quadratic residues. It has many same characteristics as the Legendre symbol. The Jacobi symbol (a/n) is defined for any odd positive integer n as follows:

If n = p1^a1p2^a2p3^a3..... pk^ak , where pi are the primes, then

(a/n) = (a/p1)^a1(a/p2)^a2.....(a/pk)^ak

Properties

If gcd(a,n) = 1 and ‘a’ is a square mod n, where n is an odd positive integer, then (a/n) = 1, but the converse is not true.

Let a,b be integers and m,n be positive odd integers

1. If a ≡ b (mod n), then, a/n=b/n 
    
2.  (ab/n) =  (a/n )( b/n )
    
3.  (a/mn) =  (a/m )( a/n )
    
4. (-1/n) = -1^(n-1)/2, so if and only if n ≡ 1 mod 4, it is 1.
    
5. (2/n) = -1^(n*n-1)/8,  if and only if n ≡ ±1 mod 8, it is 1.
    
6. (m/n)(n/m) = -1^{(n-1)/2.(m-1)/2}, if m and n are coprime positive odd integers.

C++ Code for Jacobi Symbol

#include <bits/stdc++.h>
using namespace std;

int calculateJacobiSymbol(long long a, long long n){
	if (!a)
		/* 0/n= 0 */
		return 0;  
		
	int res = 1;
	if (a < 0){
    	/*a/n= -(a/n) * -(1/n) */
		a = -a; 
		if (n % 4 == 3)
    		/* -(1n)=-1 if n= 3 (mod 4) */
			res= -res; 
	}

	if (a == 1)
    	/* (1/n) = 1 */
		return res;

	while (a){
		if (a < 0){
    		/*a/n= -(a/n) * -(1/n) */
			a = -a;
			if (n % 4 == 3)
            	/* -(1/n)=-1 if n= 3 (mod 4) */
				res = -res;
	}

	while (a % 2 == 0){
		a = a / 2;
		if (n % 8 == 3 || n % 8 == 5)
			res= -res;
	}
	swap(a, n);

	if (a % 4 == 3 && n % 4 == 3)
		res= -res;
	a = a % n;

	if (a > n / 2)
		a = a - n;
	}

	if (n == 1)
		return res;
		
	return 0;
}

int main(){
	int a= 1235;
	int n=10007;
    cout<< calculateJacobiSymbol(a, n);
}

You can also try this code with Online C++ Compiler

Run Code

Output: -1

We hope you have learned everything about the Legendre and Jacobi Symbol. 

Frequently Asked Questions

What are the Legendre and Jacobi symbols?

The Legendre symbol is a function that stores information about whether an integer is the quadratic residue modulo an odd prime. The Jacobi symbol is used to simplify computations involving quadratic residues. It shares many same characteristics as the Legendre symbol. 

What are the values given as output by the Legendre and Jacobi symbols?

The output given by the Legendre and Jacobi symbols are -1, 0, and 1.

How is the Legendre symbol represented?

The Legendre symbol is represented as a/p, where ‘p’ is the odd prime, and ‘a’ is an integer.

How is the Jacobi symbol represented?

The Jacobi symbol is represented as a/n, where ‘n’ is a positive odd integer, and ‘a’ is an integer.

What is quadratic residue?

If m and n are coprime integers, then m is called a quadratic residue modulo n if the congruence y² ≡ m(mod n)has a solution.

Conclusion

In this article, we explored the Legendre and Jacobi symbols. We explored different properties of Legendre and Jacobi symbols. To learn more about articles like Legendre and Jacobi symbols, check out more articles on cryptography as follows

• What is Identity-based Cryptography?
• Cryptanalysis of Substitution Cipher
• Cryptanalysis of Hill Cipher
• Security in Cryptography

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, System Design, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to the problems available and mock tests. Take a look at the interview bundle and interview experiences for placement preparations.

Happy Learning Ninja!