Tonelli-Shanks アルゴリズムの理解と実装(2) - Qiita

はじめに 前回の記事はこちらです。 実装 まず、今回仮定する条件をもう一度しておきます。 Input: $p$ : 奇素数 $n$ : 整数, ただし$n$は$p$の倍数ではない Output: $x$ : $x^2 \equiv n\ {\rm mod}\ p$, かつ $0 < x < n$を満たす1 $n$が$p$の倍数なら、$n \equiv 0\ {\rm mod}\ p$で剰余とは言いづらいので今回は除外します(例外としてコード中に組み込みます)。 Legendre記号 $$\left(\begin{array} nn\ p \end{array}\right) := n^{\frac{p-1}{2}} \equiv \begin{cases} 1\ {\rm mod}\ p\Leftrightarrow n は平方剰余\ -1\ {\rm mod}\ p \Leftright