# Tonelli-Shanks Algorithm

The **Tonelli–Shanks algorithm** is a classical and efficient method to compute modular square roots over finite fields $$\mathbb{F}\_{p^m}$$, especially when $$m$$ is odd and $$p \equiv 1 \pmod 4$$, where simpler methods like Shanks do not apply. The method is based on *Algorithm 5* from [ePrint 2012/685](https://eprint.iacr.org/2012/685.pdf).

***

## Preconditions

To use Tonelli–Shanks:

* $$m$$ must be **odd**.
* $$p$$ must be an **odd prime**
* $$a$$ is a **quadratic residue**.

We express $$p - 1$$ as:

$$
p - 1 = 2^s \cdot T
$$

where $$T$$ is odd.

This decomposition is known as the **2-adic decomposition** of $$p−1$$, and $$s$$ is the **2-adicity**.

***

## Algorithm Steps (High-level)

Let’s outline the algorithm assuming $$a \in \mathbb{F}\_{p^m}^\*$$:

1. **Precomputation**
   * Write $$p - 1 = 2^s \cdot T$$
   * Find a known **quadratic non-residue** $$c \in \mathbb{F}\_{p^m}$$
   * Compute $$z = c^T$$ — a $$2^s$$-th primitive root of unity
2. **Initial values**
   * $$x = a^{(T+1)/2}$$
   * $$b = a^T$$
   * $$v = s$$
3. **Main loop**
   * While $$b \ne 1$$, do:
     * Find the smallest $$k$$ such that $$b^{2^k} \equiv 1$$
     * Let $$w = z^{2^{v - k - 1}}$$
     * Update:

       $$
       x \leftarrow x \cdot w,\quad
       b \leftarrow b \cdot w^2,\quad
       z \leftarrow w^2,\quad
       v \leftarrow k
       $$
4. **Output**
   * $$x$$ is the square root of $$a$$

***

### Intuition Behind the Updates in Tonelli–Shanks

The Tonelli–Shanks algorithm iteratively computes the square root of a quadratic residue $$a \in \mathbb{F}\_p$$, given the decomposition $$p - 1 = 2^s \cdot T$$, with $$T$$ odd. Its central mechanism relies on maintaining a key invariant and gradually reducing the complexity of the problem step by step.

***

#### Invariant: $$x\_i^2 = a \cdot b\_i$$

At each iteration $$i$$, the algorithm maintains:

$$
x\_i^2 = a \cdot b\_i
$$

We define:

* $$x\_0 = a^{(T+1)/2}$$
* $$b\_0 = a^T$$
* Then:

  $$
  x\_0^2 = a^{T+1} = a \cdot a^T = a \cdot b\_0
  $$

**Inductive step**: Suppose at iteration $$i$$, the invariant holds:

$$
x\_i^2 = a \cdot b\_i
$$

Then the algorithm updates:

$$
\begin{aligned}
w\_i &= z^{2^{v\_i - k\_i - 1}} \\
x\_{i+1} &= x\_i \cdot w\_i \\
b\_{i+1} &= b\_i \cdot w\_i^2
\end{aligned}
$$

Then we have:

$$
x\_{i+1}^2 = (x\_i w\_i)^2 = x\_i^2 \cdot w\_i^2 = (a \cdot b\_i) \cdot w\_i^2 = a \cdot (b\_i \cdot w\_i^2) = a \cdot b\_{i+1}
$$

Therefore, the invariant is preserved at every step:

$$
x\_i^2 = a \cdot b\_i
$$

***

### Why $$b\_i \to 1$$: Convergence of the Loop

At each iteration of Tonelli–Shanks, the algorithm updates:

$$
b\_{i+1} = b\_i \cdot w\_i^2
$$

To show that $$b\_i \to 1$$, we analyze how the order of $$b\_i$$ decreases over time. Suppose that at iteration $$i$$, the smallest integer $$k$$ such that $$b\_i^{2^k} = 1$$, and $$b\_i^{2^{k-1}} \ne 1$$. Then $$b\_i$$ is a **primitive**  $$2^k$$**-th root of unity**.

We now prove that the update:

$$
b\_{i+1} = b\_i \cdot w\_i^2
\quad \text{with} \quad
w\_i = z^{2^{v - k - 1}}
$$

forces $$b\_{i+1}$$ to have strictly lower order.

Let’s compute:

$$
\begin{aligned}
(b\_{i+1})^{2^{k-1}} &= (b\_i \cdot w\_i^2)^{2^{k-1}} \\
&= b\_i^{2^{k-1}} \cdot (w\_i^2)^{2^{k-1}} \\
&= (-1) \cdot (-1) = 1
\end{aligned}
$$

***

#### Why does this work?

* Since $$b\_i^{2^k} = 1$$ and $$b\_i^{2^{k-1}} \ne 1$$, we know by the **Halving Lemma** that $$b\_i^{2^{k-1}} = -1$$
* Now for $$w\_i$$, recall that:

  $$
  w\_i = z^{2^{v - k - 1}} \Rightarrow w\_i^2 = z^{2^{v - k}}
  $$

  Then:

  $$
  (w\_i^2)^{2^{k-1}} = z^{2^{v - k} \cdot 2^{k-1}} = z^{2^{v - 1}} = -1
  $$

  because $$z$$ is a **quadratic non-residue**, and by construction(when $$i = 0, v= s$$):

  $$
  z^{2^{s-1}} = \left(c^T\right)^{2^{s-1}} = c^{2^{s-1}\cdot T} = -1
  $$

  This identity continues to hold at every step due to the invariant:

  $$
  z\_i^{2^{v - 1}} = -1
  $$

***

#### Result

Since both $$b\_i^{2^{k - 1}} = -1$$ and $$(w\_i^2)^{2^{k - 1}} = -1$$, their product is 1:

$$
(b\_i \cdot w\_i^2)^{2^{k - 1}} = 1
$$

Thus, the order of $$b\_{i+1}$$ is now at most $$2^{k - 1}$$, which is strictly less than the order of $$b\_i$$. As a result, the order of $$b$$ decreases with each iteration, and within at most $$s$$ steps, we reach:

$$
b\_{\text{last}} = 1
$$

Once this happens, the invariant $$x^2 = a \cdot b$$ gives $$x^2 = a$$, completing the algorithm.

> Written by [Ryan Kim](mailto:undefined) of Fractalyze


---

# 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://fractalyze.gitbook.io/intro/primitives/modular-arithmetic/modular-square-root/tonelli-shanks-algorithm.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.