# 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)  */
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/quadratic-residues.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.