Tonelli-Shanks

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

Tonelli-Shanks doesn't work for composite (non-prime) moduli. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it's a hard problem.

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

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

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

Significance of 3mod4 in squares and square roots mod n?Cryptography Stack Exchange