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\).
Quadratic residues with Jacobi and Legendre symbol |
Theory
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:
- 1. When \(a\) is a quadratic residue of \(p\).
- -1. When \(a\) is a quadratic nonresidue of \(p\).
- 0. When \(a\) shares a factor of \(p\).
The notation used to define this operation is \( \left(\frac{a}{p}\right) \).
Coding
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,