Quadratic residues with Jacobi and Legendre symbol
[Primes Home][Home]
A quadratic residue relates to the solving of the form: \(y = x^2 \pmod n\), and where we need to find values of \(y\) for different values of \(x\), and for a given modulus (\(n\)). For n=11, we get \(Z_p^*\)={1, 3, 4, 5, 9}. This is because, \(1^2 \pmod{11}=1\), \(2^2 \pmod{11}=4\), \(3^2 \pmod{11}=9\), \(4^2 \pmod{11}=5\), \(5^2 \pmod{11}=3\), \(6^2 \pmod{11}=3\), \(7^2 \pmod{11}=5\), \(8^2 \pmod{11}=9\), \(9^2 \pmod{11}=4\), and \(10^2 \pmod{11}=1\).
|
A quadratic residue relates to the solving of the form: \(y = x^2 \pmod n\), and where we need to find values of \(y\) for different values of \(x\), and for a given modulus (\(n\)). For n=11, we get \(Z_p^*\)={1, 3, 4, 5, 9}. This is because, \(1^2 \pmod{11}=1\), \(2^2 \pmod{11}=4\), \(3^2 \pmod{11}=9\), \(4^2 \pmod{11}=5\), \(5^2 \pmod{11}=3\), \(6^2 \pmod{11}=3\), \(7^2 \pmod{11}=5\), \(8^2 \pmod{11}=9\), \(9^2 \pmod{11}=4\), and \(10^2 \pmod{11}=1\).
To find the quaratic residues for a given modulus, we can use the Jacobi symbol is \( \left(\frac{a}{p}\right) \), and is defined as:
\( \left(\frac{a}{p}\right) = \{ \begin{array}{rl} 0 & \text{if } a \equiv 0 \pmod{p},\\1 & \text{if } a \not\equiv 0\pmod{p} \text{ and for some integer } x\colon\;a\equiv x^2\pmod{p},\\-1 & \text{if } a \not\equiv 0\pmod{p} \text{ and there is no such } x. \end{array} \)
The legendre_symbol returns:
The notation used to define this operation is \( \left(\frac{a}{p}\right) \).
The coding is here:
import sys import libnum def legendre_symbol(a, p): """ Compute the Legendre symbol a|p using Euler's criterion. p is a prime, a is relatively prime to p (if p divides a, then a|p = 0) Returns 1 if a has a square root modulo p, -1 otherwise. """ ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else ls n=11 if (len(sys.argv)>1): n=int(sys.argv[1]) print ("Here are the Z*p (quadratic residues modulo n and coprime to n):") print ("\nJacobi symbol") for a in range(1, n): rtn= libnum.jacobi(a,n) if (rtn==1): print (a,end=', ') print ("\nLegendre symbol") for a in range(1, n): rtn= legendre_symbol(a,n) if (rtn==1): print (a,end=', ')
A sample run:
N= 31 Here are the Z*p (quadratic residues modulo n and coprime to n): Jacobi symbol 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28, Legendre symbol 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28,