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'