# Shanks & Tonelli

Pseudocode for the method of Shanks and Tonelli for the computation of square roots in respect to prime moduli is presented below. Let (a|p) denote the Legendre symbol of a (modulo p).
``` Input: elements a and p.
Output: x such that x^2 == a (mod p), or 'UNSOLVABLE', if no such solution exists.

0. if (a == 0) return 0 else if (a|p) == -1 return 'UNSOLVABLE'.
1. chose any n with (n|p) == -1.
2. decompose p-1 into two integers r,q with p-1 == q*(2^r) and q odd.
3. let y = n^q.
4. let b = a^((q-1)/2).
5. let x = a*b.
6. let b = b*x.
7. while (b != 1)
7.1. find smallest m with b^(2^m) == 1.
7.2. let t = y^(2^(r-m-1)).
7.3. let y = t^2.
7.4. let r = m.
7.5. let x = x*t.
7.6. let b = b*y.
8. return x.
```

### Notes:

• All computations are meant modulo p. For instance, step 5 has to be read as 'let x = a*b (mod p)'.
• Steps 1, 2 and 3 may be seen as a 'precomputation step', depending solely on p.
• A good strategy to find n in step 1 might be to try values counting upwards from n == 2.
• This algorithm is based on algorithm II.8 (page 18) in Elliptic Curves in Cryptography, Blake, Seroussi, Smart, Cambridge Press, 2000.
• If p = 3 (mod 4) or p = 5 (mod 8) the following algorithms (found in IEEE P1363, Annex A) perform slightly better than the one given above. Note that the third algorithm given in P1363 (suitable for primes p = 1 (mod 8) is typically outperformed by Shanks & Tonelli by factors of 4-20.
``` Input: elements a and p with p = 3 (mod 4).
Output: x such that x^2 == a (mod p), or 'UNSOLVABLE', if no such solution exists.

0. let k = (p + 1) / 4 = (p >> 2) + 1.
1. let x = a ^ k
2. if (x ^ 2 == a)
return x
else
return 'UNSOLVABLE'
```
``` Input: elements a and p with p = 5 (mod 8).
Output: x such that x^2 == a (mod p), or 'UNSOLVABLE', if no such solution exists.

0. let k = (p - 5) / 8 = p >> 3.
1. let g = (2 * a) ^ k
2. let i = 2 * a * (g ^ 2)
3. let x = a * g * (i - 1)
4. if (x ^ 2 == a)
return x
else
return 'UNSOLVABLE'
```