Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Legendre Symbol
2.1.
Properties
3.
Jacobi Symbol
3.1.
Properties
3.2.
C++ Code for Jacobi Symbol
4.
Frequently Asked Questions
4.1.
What are the Legendre and Jacobi symbols?
4.2.
What are the values given as output by the Legendre and Jacobi symbols?
4.3.
How is the Legendre symbol represented?
4.4.
How is the Jacobi symbol represented?
4.5.
What is quadratic residue?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Legendre and Jacobi Symbols

Author Aashna Luthra
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Welcome Ninjas! Do you want to know how to encode the information about whether a number given is a quadratic residue modulo an odd prime? This is implemented by Legendre and Jacobi symbols.

intro image

Are you interested in knowing more about Legendre and Jacobi symbols? Great! You are at the right place. Let us first start with the Legendre symbol.

Legendre Symbol

The Legendre symbol is a function that stores information about whether an integer is a quadratic residue modulo an odd prime. To make notation simpler, it is applied in the law of quadratic reciprocity. The Legendre symbol is an excellent tool for performing computations and providing answers related to quadratic residues.

Note - An integer r is called a quadratic residue modulo m in number theory if it is congruent to a perfect square modulo m; i.e., if there exists an integer y such that: y2 ≡ r (mod m).


Let ‘p’ be an odd prime and ‘a’ be an integer and . The Legendre symbol ‘a’ with respect to ‘p’ is defined by
 

            1      if a ≡ 0 (mod p) and ‘a’ is a quadratic residue modulo p 

(a/p) = -1      if a is the quadratic non-residue modulo p

             0      if a ≡ 0 (mod p)

Note - The Legendre symbol ap looks like a fraction, but it’s not.

Example 1:

from sympy.ntheory import legendre_symbol
[legendre_symbol(i, 11) for i in range(11)]


Output: [0, 1, -1, 1, 1, 1, -1, -1, -1, 1, -1]

Example 2:

from sympy.ntheory import legendre_symbol
[legendre_symbol(i, 5) for i in range(5)]


Output: [0, 1, -1, -1, 1]

Properties

  1. If "a" is an integer which is not divisible by "p" and "p" is an odd prime(Euler's criterion), then, a(p-1)/2= (a/p) (mod p)
     
  2. If a ≡ b (mod p), then, (a/p) = (b/p) 
     
  3.  (ab/p) =  (a/p )( b/p )
     
  4. (-1/p) = -1(p-1)/2so iff p ≡ 1 mod 4, it is 1.
     
  5. (2/p) = -1(p*p-1)/8, so for an odd prime p, only if p ≡ ±1 mod 8, it is 1.
     
  6. (q/p)(p/q) = -1(p-1)/2.(q-1)/2
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 = p1a1p2a2p3a3..... pkak , 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)/2so 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);
}


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 y2 ≡ 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


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!

Previous article
What is Primality testing?
Next article
What is Solovay-Strassen Algorithm?
Live masterclass