Tonelli–Shanks Algorithm

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 r² ≡ n (mod p), where p is a prime: that is, to find a square root of n modulo p.

x=log_\alpha\beta(mod~p)

m=\lceil (p-1)^{1/2} \rceil

1)\quad0 \le j \le (m-1)~~olmak~üzere\\
\alpha^{mj}(mod~p)~~hesaplanır.

2)\quad j,a^{mj}(mod~p) m sıralı çiftleri II koordinata göre sıralanarak L_1 listesi oluşturulur.

3)\quad 0 \le i \le (m-1) olmak üzere, 2)\quad \beta-\alpha^{-1} hesaplanır.

4)\quad (i,\beta\alpha^{-i}(mod~p)) m sıralı çiftleri II. koordinata göre sıralanarak L_2 listesi oluşturulur.

5)\quad (j,y) \in L_1 ~ve~(i,y) \in L_2 bulunur

6)\quad x=\log_\alpha \beta=(mj+i)mod(p-1)