> For the complete documentation index, see [llms.txt](https://www.ctfrecipes.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/quadratic-residues.md).

# Quadratic residues

{% hint style="info" %}
This page is about modular arithmetic.\
\
The integers modulo `p` define a field, denoted `Fp`.\\

A finite field `Fp` is the set of integers `{0,1,...,p-1}`, and under both addition and multiplication there is an inverse element `b` for every element `a` in the set, such that\
`a + b = 0` and `a * b = 1`.
{% endhint %}

A quadratic residue is a number that is the result of squaring another number. In other words, a number **`x`** is a quadratic residue (modulo **`p`**) if there exists another number **`a`** such that

$$
x^2 \equiv a \bmod p
$$

The set of all quadratic residues modulo \*\*`p` \*\* is called the **set of quadratic residues** of **`p`**.

{% hint style="info" %}
**The concept of quadratic residues is important in number theory and cryptography**.

For example, the problem of finding quadratic residues is known as the "**quadratic residue problem**", and it is a hard problem in the sense that solving it for large integers is **computationally infeasible**.

This makes it useful for **creating secure encryption algorithms**.
{% endhint %}

Here is an example :

An integer `a=21` has the following square mod 31 : `a² ≡ 7 mod 31` .

As `a = 21, a² = 7` , the square root of **`7`** is **`21`**

{% hint style="warning" %}
Note : For the elements of `Fp`, <mark style="color:red;">**not every element has a square root**</mark>. In fact, what we find is that **for roughly one half of the elements** of `Fp`, **there is no square root.**

Theses elements are called **quadratic non-residue**
{% endhint %}

## Interesting properties

```
Quadratic Residue * Quadratic Residue = Quadratic Residue
Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue
```

## Legendre Symbol

There is a method to determine **if an integer is a quadratic residue or not** with a single calculation thanks to Legendre.

$$
\frac{a}{p} \equiv a^{\frac{p-1}{2}} \bmod p
$$

This equation obeys :

```
(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a / p) = -1 if a is a quadratic non-residue mod p
(a / p) = 0 if a ≡ 0 mod p
```

Which means given any integer `a`, calculating `pow(a,(p-1)//2,p)` is enough to determine if `a` is a quadratic residue.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/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.