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