The Square root (mod p) of n is a number (or more properly, residue class), a, that solves the equation

a2=n (mod p).

If n is a quadratic residue (mod p), which just means if n is the square of some number (mod p), then the Shanks-Tonelli algorithm can find the number whose square is n.

Special cases: square root of -1Edit

Main article: Square root of -1 (mod p)

We shall see that the square root of -1 (mod p) exists, as long as p is of the form 4k+1. Fermat's little theorem tells us that all the elements of {1, 2, ..., p-1} are roots of the polynomial xp-1−1 = 0 (mod p). We can factor

xp-1−1 = (x(p-1)/2+1)(x(p-1)/2−1),

each factor of which has at most (p-1)/2 roots, and together having exactly p-1 roots, so each factor has exactly (p-1)/2 roots, assuring not just the existence but the plentiful supply of such an x where x(p-1)/2=-1, so the square roots of -1 are ±x(p-1)/4.

Shanks-Tonelli algorithmEdit