> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-mcs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/quadratic-residues.md).

# Quadratic Residues

Let $$n$$ be a positive integer and let $$a$$ be an integer such that $$gcd(a, n) = 1$$.

$$a$$ is said to be a quadratic residue modulo $$n$$ if and only if there exists a $$x$$ such that: $$x² \equiv a (mod n)$$

When $$n$$ is a prime number $$(n = p)$$ there exist three cases:

1. either $$a$$ is a multiple of $$p$$, or
2. $$a$$ is a quadratic residue, or
3. $$a$$ is not a quadratic residue.

The **Legendre** symbol $$(\frac{a}{p})$$ captures this as follows.

<figure><img src="/files/6RDTCEGLy9601xtfh7Ca" alt=""><figcaption></figcaption></figure>

## Legendre Symbol

<figure><img src="/files/hplc2ZxTAcAgMS7bBsnO" alt=""><figcaption></figcaption></figure>

<figure><img src="/files/wephEJBjXQG3nY3FAXqz" alt=""><figcaption></figcaption></figure>

## Jacobi Symbol

<figure><img src="/files/O5TI7qwGaaj5LT8DUAob" alt=""><figcaption></figcaption></figure>

## Counts

For a prime $$p$$, the number of integers belonging to the set $$\[1, 2, . . . , p − 1]$$ that are quadratic residues is exactly $$(p − 1)/2$$.

```
a(n)=local(v,s);v=vector(eulerphi(n));s=0;\
for(k=1,n,if(gcd(k,n)==1,s=s+1;v[s]=k;););return(v);
qr(n)=local(v);v=a(n); /* number (#) of true quadratic residues */\
return(length(Set(vector(length(v),k,(v[k]^2)%n))));
j(n)=local(v,c);v=a(n); /* # of true or fake quadratic residues */\
return(sum(k=1,length(v),kronecker(v[k],n)==1));
f(n)=return([eulerphi(n),qr(n),j(n)]);
f(101) /* returns [100,50,50] */
f(103) /* returns [102,51,51] */
f(107) /* returns [106,53,53] */
f(109) /* returns [108,54,54] */
```

How about composite numbers that are the product of two distinct prime numbers?

```
f(13*17) /* returns [192,48,96] --- half are fakes! */
f(11*13) /* returns [120,30,60] --- half are fakes! */
f(11*19) /* returns [180,45,90] --- half are fakes! */
```

## Square Roots

<figure><img src="/files/nV1UYegWsnbv1gjPqaT1" alt=""><figcaption></figcaption></figure>

Example:

```
p=11; q=19; n=p*q; r=20; a=lift(Mod(r^2,n));
rp=lift(Mod(a,p)^((p+1)/4)); rq=lift(Mod(a,q)^((q+1)/4));
r1=lift(chinese(Mod( rp,p),Mod( rq,q))); /* 20, (r1/p)=+1, (r1/q)=+1 */
r2=lift(chinese(Mod( rp,p),Mod(-rq,q))); /* 75, (r2/p)=+1, (r2/q)=-1 */
r3=lift(chinese(Mod(-rp,p),Mod( rq,q))); /* 134, (r3/p)=-1, (r3/q)=+1 */
r4=lift(chinese(Mod(-rp,p),Mod(-rq,q))); /* 189, (r4/p)=-1, (r4/q)=-1 */
```

### Factorization

<figure><img src="/files/MKsAQfMTsJWLmWsk2Xhf" alt=""><figcaption></figcaption></figure>

Example (continuation of the code of the previous slide):

```
p=11; q=19; n=p*q;
r1=20; r2=75; r3=134; r4=189; /* square roots of 191 */
gcd(r1-r2,n);                 /* 11 */
gcd(r1+r2,n);                 /* 19 */
```

**pari-gp** can only compute square roots when the modulus is prime:

```
sqrt(Mod(5,11))    /* ok (because 5 is a quadratic residue)     */
sqrt(Mod(9,14))    /* error (because the modulus is not prime)  */
```