solution

Căn bậc hai modular (thuật toán Tonelli–Shanks)

Cho số nguyên tố lẻ $p$, hãy tìm $x$ thỏa:

$x^2 \equiv a \pmod p$

Nghiệm tồn tại khi $a\equiv0$ hoặc $a$ là thặng dư bậc hai (ký hiệu Legendre bằng $1$). Khi $p\equiv3\pmod4$ có công thức nhanh $x=a^{(p+1)/4}$; trường hợp chung dùng Tonelli–Shanks.

Cho $a$, $p$. In nghiệm nhỏ hơn trong hai nghiệm $\{x, p-x\}$. Nếu vô nghiệm, in $-1$.

Ví dụ

$x^2\equiv2\pmod7$: $3^2=9\equiv2$ và $4^2=16\equiv2$, nghiệm nhỏ hơn là $3$.