# Tonelli-Shanks

In a congruence of the form `r2 ≡ a mod p`, Tonelli-Shanks calculates `r`.

{% hint style="danger" %}
Tonelli-Shanks <mark style="color:red;">**doesn't work for composite (non-prime) moduli**</mark>. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it's a hard problem.
{% endhint %}

The main use-case for this algorithm is finding elliptic curve co-ordinates. Its operation is somewhat complex so we're not going to discuss the details. But there is a python implementation

{% code lineNumbers="true" %}

```python
def legendre(a,p):
    return pow(a, (p-1) // 2,p)

def tonelli(a,p):
    assert(legendre(a,p) ==1, "not a quadratic-residue")
    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1

    if s == 1 :
        return pow(a, (p + 1)//4, p)

    for z in range(2, p):
        if p - 1 == legendre(z, p):
            break

    c = pow(z, q, p)
    r = pow(a, (q+1) // 2, p)
    t = pow(a, q, p)

    m = s

    t2 = 0

    while (t - 1) % p != 0:
        t2 = (t * t) % p
        for i in range(1, m):
            if (t2 -1) % p == 0:
                break
            t2 = (t2 * t2) % p
        b = pow(c, 1 << (m - i - 1), p)
        r = (r * b) % p
        c = (b * b) % p
        t = (t * c) % p
        m = i
    return r
```

{% endcode %}

Note the line 13 ? If `s == 1` it's possible to quickly get the square root value with the following equation :

$$
\sqrt a = a^{\frac{p+1}{4}} \bmod p
$$

This occur cause a property of primes numbers : all primes that aren't 2 are of the form `p ≡ 1 mod 4` or `p ≡ 3 mod 4`, since all odd numbers obey these congruences.

Take a look the case `p ≡ 3 mod 4` with a [Fermat's little theorem](/cryptography/general-knowledge/maths/modular-arithmetic/fermats-little-theorem.md) derivation

$$
(a^{\frac{p+1}{4}})^2 \equiv a^{\frac{p+1}{2}} \equiv a^{(\frac{p-1}{2}+1)} \equiv a^{\frac{p-1}{2}} \cdot a \mod p
$$

It's possible cause `p + 1` is divisible by 4 unlike the case `p ≡ 1 mod 4` and `a` is a quadritic residue so it follows that :

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

## Resources

{% embed url="<https://crypto.stackexchange.com/questions/20993/significance-of-3mod4-in-squares-and-square-roots-mod-n/20994#20994>" %}


---

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