# Shanks Algorithm

When the prime modulus $$p$$ satisfies $$p \equiv 3 \pmod 4$$, computing the square root of a quadratic residue $$a \in \mathbb{F}\_{p^m}$$ becomes remarkably simple when $$m$$ is **odd**. This is because the field size $$q = p^m$$ then satisfies $$q \equiv 3 \pmod 4$$, enabling a shortcut formula for extracting square roots. The method is based on Algorithm 2 from [ePrint 2012/685](https://eprint.iacr.org/2012/685.pdf).

***

## Goal

Find $$x \in \mathbb{F}\_{p^m}$$ such that:

$$
x^2 = a
$$

if $$a$$ is a quadratic residue.

***

## Original Algorithm

The algorithm consists of the following steps:

1. Compute $$a\_1 = a^{(p - 3)/4}$$
2. Compute $$a\_0 = a\_1^2 \cdot a = a^{(p-1) / 2}$$
3. If $$a\_0 = -1$$, then $$a$$ is a quadratic nonresidue
4. Otherwise, return $$x = a\_1 \cdot a = a^{(p + 1)/4}$$

This version performs:

* 1 exponentiation,
* 1 squaring,
* 2 multiplications.

***

## Modified Algorithm

A simplified version is often used in practice:

1. Compute $$x = a^{(p + 1)/4}$$
2. If $$x^2 = a$$, return $$x$$
3. Otherwise, $$a$$ is a quadratic nonresidue

This version only requires:

* 1 exponentiation,
* 1 squaring

and defers the residuosity check to a final comparison.

***

### Why It Works (when $$m = 1$$)

To understand why this shortcut is valid, consider the case where $$a \in \mathbb{F}\_p$$ and $$p \equiv 3 \pmod 4$$. Suppose $$x$$ is a square root of $$a$$, i.e.,

$$
x^2 = a
$$

Then,

$$
x^4 = (x^2)^2 = a^2
$$

We know:

$$
a^2 = a^{p+1} \mod p
$$

But since $$p \equiv 3 \pmod 4$$,  taking the 4th root of both sides gives:

$$
x = a^{(p+1)/4}
$$

Therefore, $$x = a^{(p+1)/4}$$ is indeed a valid square root of $$a \mod p$$ — if $$a$$ is a quadratic residue.

***

### Why It Requires $$m$$ to Be Odd

In the general case over $$\mathbb{F}\_{p^m}$$, we require the field size $$q = p^m$$ to satisfy $$q \equiv 3 \pmod 4$$ for the exponent $$(q+1)/4$$ to be an integer and the formula to hold. This congruence only holds when:

* $$p \equiv 3 \pmod 4$$, and
* $$m$$ is odd

For example:

* If $$p = 3$$, then:
  * $$3^1 \equiv 3 \pmod 4$$ ✅ (odd $$m = 1$$)
  * $$3^2 = 9 \equiv 1 \pmod 4$$ ❌ (even $$m = 2$$)

So this algorithm is only valid when both conditions are met.

> 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/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.