Shanks-Tonelli
Daniel Shanks (1917-1996) was an absolute master at devising and modifying algorithm for computing using quadratic forms, number fields, modular arithmetic and ordinary arithmetic. One of s cleverest pieces of work was s modifications to an old procedure to find modular square roots in 1973 wch was first developed by Alberto Tonelli in 1891 wch is an equivalent, slightly more redundant version of the algorithm.
The Shanks-Tonelli algorithm is a procedure used with in modular arithmetic for solving a congruence of the form $k^{2}\equiv q\, \: \left ( mod\,\, p \right )$, where p is an odd prime and q is a quadratic residue $\left ( mod\,\, p \right )$ In other words, it is used to compute square roots in the finite field Z/pZ (wch means, every Congruence class except zero modulo p has a multiplicative inverse. Ts is not true for composite moduli.). Hence, Shanks-Tonelli algorithm cannot be implemented for composite moduli; finding square roots modulo composite numbers is a computational problem.
