補足：法2017における(-1)の平方根の計算

本日アップロードしたばかりのこちらの記事
tsujimotter.hatenablog.com

では

$X^2 \equiv -1 \pmod{2017}$

を計算する効率的な方法がわからない、と書いていました。

先ほど nishimura さんという方に*1効率的な方法を教えていただきましたので、その方法を補足したいと思います。

「オイラーの基準」や「平方剰余の相互法則」といった初等整数論の知識は仮定します。

計算方法

まず、考えたいのはオイラーの基準です。一般に奇素数 $p$ に対して

$\displaystyle \left(\frac{b}{p}\right) \equiv b^{\frac{p-1}{2}} \pmod{p}$

が成り立ちます。

ここでもし、 $b$ として $p$ の平方非剰余なる数をとれば、左辺のルジャンドル記号が $-1$ になりますから、

$b^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

が得られます。

したがって

$\left(b^{\frac{p-1}{4}}\right)^2 = b^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

より、 $X = b^{\frac{p-1}{4}}$ とすれば、

$X^2 \equiv -1 \pmod{p}$

を満たす $X$ が見つけられたことになります。

平方非剰余であるような $b$ は、 $1$ から $p-1$ のうち半分ですから、適当に探せばすぐに見つかります。

今回は平方剰余の相互法則を簡単化する都合上、 $b$ として特に奇素数を選んで探索することにします*2。

実際、 $p = 2017$ のときは $b = 5$ という平方非剰余が見つかります。平方剰余の相互法則より

$\displaystyle \left(\frac{5}{2017}\right) = \left(\frac{2017}{5}\right) = \left(\frac{2}{5}\right) = -1$

となり、たしかに平方非剰余ですね。

あとは、この $b = 5$ を使って

$5^{504} \pmod{2017}$

を計算すればよいでしょう。

以上のような「べき剰余」の計算方法は、以下の記事
tsujimotter.hatenablog.com

でたくさん紹介したことがありましたが、今回は別の方法「繰り返し二乗法」を用います。

指数 $504$ を二進展開すると

$504 = 111111000_{(2)} = 256 + 128 + 64 + 32 + 16 + 8$

と表せます。

こうしておくと

$5^{504} = 5^{256 + 128 + 64 + 32 + 16 + 8} = 5^{256} \cdot 5^{128} \cdot 5^{64} \cdot 5^{32} \cdot 5^{16} \cdot 5^{8}$

とかけますから「５の「２のべき乗」乗」だけ計算すればよいことがわかります。５の「２のべき乗」乗は、

$5^2$

$5^4 = (5^2)^2$

$5^8 = (5^4)^2$

という具合に、繰り返し自身を２乗していくことで、簡単に得られます。

とはいえ、やってみたところ手計算ではつらかったので（ $5^8 = 390625$ のあたりで断念しました）、ここはコンピュータの力をお借りします。

 5^2 == 25 mod 2017
 5^4 == 625 mod 2017
 5^8 == 1344 mod 2017
 5^16 == 1121 mod 2017
 5^32 == 50 mod 2017
 5^64 == 483 mod 2017
 5^128 == 1334 mod 2017
 5^256 == 562 mod 2017

よって

$\begin{align} 5^{504} &= 5^{256 + 128 + 64 + 32 + 16 + 8} \\ & \equiv 562\cdot 1334 \cdot 483 \cdot 50 \cdot 1121 \cdot 1344 \\ & \equiv 229 \pmod{2017} \end{align}$