The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n (mod p), where p is a prime: that is, to find a square root of n modulo p. The Tonelli–Shanks algorithm cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly more redundant version of this algorithm was developed by Alberto Tonelli in 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained:
My tardiness in learning of these historical references was because I had lent Volume 1 of Dickson's History to a friend and it was never returned.
According to Dickson, Tonelli's algorithm can take square roots of x modulo prime powers pλ apart from primes.
Core ideas Given a non-zero n {\displaystyle n} and a prime p > 2 {\displaystyle p>2} (which will always be odd), Euler's criterion tells us that n {\displaystyle n} has a square root (i.e., n {\displaystyle n} is a quadratic residue) if and only if:
n p − 1 2 ≡ 1 ( mod p ) {\displaystyle n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}} . In contrast, if a number z {\displaystyle z} has no square root (is a non-residue), Euler's criterion tells us that:
z p − 1 2 ≡ − 1 ( mod p ) {\displaystyle z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} . It is not hard to find such z {\displaystyle z} , because half of the integers between 1 and p − 1 {\displaystyle p-1} have this property. So we assume that we have access to such a non-residue. By (normally) dividing by 2 repeatedly, we can write p − 1 {\displaystyle p-1} as Q 2 S {\displaystyle Q2^{S}} , where Q {\displaystyle Q} is odd. Note that if we try
R ≡ n Q + 1 2 ( mod p ) {\displaystyle R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}} , then R 2 ≡ n Q + 1 = ( n ) ( n Q ) ( mod p ) {\displaystyle R^{2}\equiv n^{Q+1}=(n)(n^{Q}){\pmod {p}}} . If t ≡ n Q ≡ 1 ( mod p ) {\displaystyle t\equiv n^{Q}\equiv 1{\pmod {p}}} , then R {\displaystyle R} is a square root of n {\displaystyle n} . Otherwise, for M = S {\displaystyle M=S} , we have R {\displaystyle R} and t {\displaystyle t} satisfying:
R 2 ≡ n t ( mod p ) {\displaystyle R^{2}\equiv nt{\pmod {p}}} ; and
… excerpt ends here. Continue reading the full article.
