Tonelli–Shanks computes a square root of a quadratic residue a modulo an odd prime p. Use the power shortcut when p ≡ 3 mod 4; use Tonelli–Shanks when p ≡ 1 mod 4. section 2.5 section 2.7
For p ≡ 1 mod 4, the implementation proceeds as follows:
- Factor p − 1 as 2^e q with q odd by scanning the low zero bits and repeatedly dividing by two. section 2.5
- While b is not 1, find the smallest m such that b^(2^m) ≡ 1 mod p; if m = r, reject a as a nonresidue. section 2.5
- Apply t = y^(2^(r−m−1)), then update y = t², r = m, x = xt, and b = by before repeating. section 2.5
Choosing the method
To decide whether the power shortcut or Tonelli–Shanks applies, inspect the prime modulus modulo 4. The exercise asks which method handles 27213068317 after converting it to hexadecimal. section 2.5
