> 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/tonelli-shanks.md).

# 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>" %}