元祖ワシ的日記

一つ前のエントリでは

\[
x^2 = a \pmod{p}
\]

の解がわかると

\[
x^2 = a \pmod{p^2}
\]

を解くことが出来たのでした。同じ考え方で任意の$p^k$について次のようにして求めることが出来ます。

\[
(x-\sqrt{a})^k
\]
を計算して
$\sqrt{a}$の係数が$\pmod{p^k}$で1になるように逆数を乗じればokです。

$\sqrt{a}$の係数が$p$で割り切れてしまうとまずいのでそのことだけ証明しないといけませんが、結論だけから言うとその係数は
$(2u)^{k-1}$に$\mod{p}$で等しくなります。つまり$u^2=a\pmod{p}$としたとき

\[
(u_{k}-v_{k}\sqrt{a})
=(u-\sqrt{a})^k
\]
とすると

\[
v_k=(2u)^{k-1}\pmod{p}
\]
となります。よって$v_k$は$p$と互いに素で、逆数が存在することになり解を求めることが出来ます。

\[
x^2 = a \pmod{p}
\]

の解がわかると

\[
x^2 = a \pmod{p^2}
\]

を解くことができます。その手順について解説します。

$x^2 = a \pmod{p}$の解があるということは

\[
x^2 - a = up
\]

なる$u$があるということです。左辺は次のように変形することができます。

\[
(x-\sqrt{a})(x+\sqrt{a})=up
\]

両辺を二乗すれば

\[
(x-\sqrt{a})^2(x+\sqrt{a})^2=u^2p^2
\]
これより

\[
 \begin{aligned}
((x^2+a)-2x\sqrt{a})((x^2+a)+2x\sqrt{a})=u^2p^2\\
\end{aligned}
\]

を得るので$2x$で各係数を割れば

 \[
\begin{aligned}
\left(\frac{x^2+a}{2x}-\sqrt{a}\right)
\left(\frac{x^2+a}{2x}+\sqrt{a}\right)=\frac{u^2p^2}{4x^2}\\
\end{aligned}
\]

となり$\frac{x^2+a}{2x}$が解になります。最後の$2x$で割るというところが微妙ですが、これはここから$p^2$での剰余を考えて演算をするということで解決できます。

例
\[
8^2-7=3\cdot 19\\
\]
が既知とします。

\[
\begin{aligned}
(8-\sqrt{7})(8+\sqrt{7})&=3\cdot 19\\
(71-16\sqrt{7})(71+16\sqrt{7})&=3^2\cdot 19^2\\

\end{aligned}
\]

ここで
\[
16 x = 1\ \pmod{19^2}
\]
なる数を探します。すると$158$であることがわかるので左辺の各項に乗じて$19^2$での剰余を求めると

\[
(27-\sqrt{7})(27+\sqrt{7})=0  \pmod{19^2}
\]
を得ることができます。

注)
$2x$が$p$と互いに素であることが重要です。$x$はあきらかに$p$と素ですが2を乗じているので$p$は奇素数でなければなりません。

8N+1の素数について、もう一つ別の考え方を解説します。多分Tonelli–Shanksのアルゴリズムと同じ考えに基づくものと思われます。

$p-1=2^s t$(ただし$t$は奇数)とおきます。すると任意の$x$に対して
\[
(x^t)^{2^s} = 1
\]
ですから$x^t$は1の$2^t$乗根です。

例えば97を考えると
\[
96 = 2^5\cdot 3
\]
ですから $x^3$は1の32乗根です。一般的に1の32乗根は32個あり、そのうち16個が32乗してはじめて1になる数です。ある数$\omega$が32乗して初めて1になる数とすれば
$\omega^3, \omega^5, \cdots, \omega^31$もまた32乗根してはじめて1になる数です。よって1つそのような数を見つければ他の数は自然と見つかることになります。

（余談ながらその逆数$\omega^{-1}, \omega^{-3},\cdots, \omega^{-31}$も然りです） 

$\omega$を32乗して初めて1になる数（例えば42）としてその数を2乗、4乗としてこれを木の形にしてみます。（下図参照）



空白になっているところにも$2$の冪乗根があるはずですがそれは何かわからないので空欄にしておきます。また平方根についてはaが平方根の1つなら-aもまた平方根ですので剰余を0から95ではなく-48から47までの間になるように書いています。木の葉のほうから辿れば

42 → 18 → 33 → 22 → -1

です。この中に$a^3$があれば答えは簡単です。例えば$a$が$47$とすれば、$a^3=33$ですから、1つ下の$18$を使って
\[
a^3 = 33 = 18^2
\]
これより両辺に$a$をかけて
\[
a^4 = 18^2a
\]
を得て
\[
(a^2 18^{-1})^2 = a
\]

が答えになります。$18$の逆数 ($18 x =1$なる数)が出てきますがこれは普通に求めてもいいし、そもそも$18^{16-1}=27$が逆数なのでそれを利用しても簡単に求まります。
答えとしては$-12$が得られます。実際$-12^2=47$です。

そうではない場合（例えば$11$）を探す場合は次のようにします。$11^3=-27$です。$-27$を冪冪で累乗していくと

\[
\begin{eqnarray}
(-27)^2 = -47\\
(-47)^2 = -22
\end{eqnarray}
\]
となり、ここで$-22$が出ます。$-22$はツリーのルートのすぐ右側にあるので、この数はツリーの右側にあることがわかります。ところで$\omega$ですが次のような性質を持っています。

• $\omega^2$を乗ずると2段目のノードに対して左右に移動する
• $\omega^4$を乗ずると3段目のノードに対して左右に移動する
• $\cdots$
  

この性質を利用して$\omega^2(=18)$を42に乗じて(-20になる)そのノードを右側のツリーの同じ場所におきます。そしてそこからまた冪冪でルートに戻っていきます。
このルートの中に求めるノードがあればそれが答えです。残念ながら今回もみつからないので$\omega^4$を乗じます。そうすると-27が無事見つかりました。これから答えが求まります。





最後に32乗してはじめて1になる数の見つけかたですが、これは平方非剰余な数を3乗すれば求めるものになります。平方非剰余な数は全体の半数ですからランダムに選んで$(p-1)/2$乗して判定することができます。

この方法は運が悪いと沢山計算をする必要がありますが木の高さは $s$ですから最悪でも$s^2$くらいのオーダーの計算量になります。
一方葉は$2^s$のオーダでこれを全部計算するのはsが大きくなるととんでもない数になります。$s$が小さいときは非効率ですが大きくなるにつれて優位性が増すと思われます。

一つ前のエントリで8N+1型以外の素数についての平方根の計算方法を解説しました。8N+1については同じような考えで求めようとしてもなかなかうまくいきません。
\[
a^n = \pm a　（ただしnは偶数）
\]

の形になかなか持ち込めないのがその要因です。今まで考えきた演算は$p$での剰余をもって演算するもので代数学的には$F_p$で演算と呼ばれるものです。$F_p$は$p$個の元からなる有限の集合で、その元同士に加減乗除が定義されているものです。この空間で演算をしている限りこの問題をクリアすのはどうも不可能なようです。そこで発想をちょっと変えて$F_p$ではなく$F_q$で考えることにします。$F_q$とは$F_p$の世界で既約な方程式の根を追加した体（加減乗除がうまく定義された集合）です。$F_p$は$p$個の元からなる体ですが、$F_q$は$q$個の元からなるので$F_q$と表現します。今回はちなみに$q=p^2$なので、$F_{p^2}$と記述するのが正確なのかもしれませんが、とりあえず$F_q$と表現しておきます。なんか難しいこと言ってますが発想としては簡単で$F_p$での平方根が存在しない数の平方根があると仮定してそれを追加したもの・・とゆるく考えておけばよいかと思います。

例えば有理数においても$2$の平方根は存在しませんが、仮にそれを$\sqrt{2}$と書くとすれば
\[
x+y\sqrt{2}
\]
という数の集合を考えることができてその集合に対して加減乗除が定義できます。例えば上記の数は二乗することが可能で二乗した結果は

\[
(x^2+2y^2 )+ (2xy)\sqrt{2}
\]

であってその結果もまた $x + y\sqrt{2}$の形に書けることがわかります。つまり$x+y\sqrt{2}$の形の集合を考えれば全ての加減乗除はその内部で閉じておりまた完結していることになります。

$F_q$もそれと同じ原理を用います。$F_p$から平方非剰余の数を$T$1つ選びその平方根があると仮定してそれを$\sqrt{T}$と表すことにし、この数を$F_p$に追加します。この集合に対して加減乗除が成立するためには
\[
x+y\sqrt{T}
\]と表すことができる数全て集めれば証明は割愛しますが十分で実際演算が閉じてうまく定義できることがわかります。xの選び方はp通りyの選び方はp通りですからこの体は$p^2$個の元からなることになります。この$q=p^2$とするとこの集合に対してもフェルマーの小定理が存在し

\[
x^q=x
\]

が成立することが知られています。つまり$F_q$では$q$乗すると元に戻ります。ところで$F_p$では

\[
x^p=x
\]

が成立しました。したがって$F_q$で任意の元を$p$乗すると、$F_p$に含まれる数はその位置を変えません（固定される）。しかし$F_p$に含まれない数はそうではなく、別な数に移動しますがその数は共役元になることが知られています。つまり
\[
(x+y\sqrt{T})^p = (x-y\sqrt{T})
\]
です。となれば$F_q$では任意の元を$p+1$乗すると

\[
(x+y\sqrt{T})^{p+1} = (x+y\sqrt{T})(x-y\sqrt{T}) = x^2 -y^2 T
\]

となりその数がなんであり$F_p$に属することになります。今

\[
x^2 -y^2 T=a
\]
となるようにうまく$x,y$を選ぶことができれば$p+1$は奇数ですから

\[
(x+y\sqrt{T})^\frac{p+1}{2}
\]

がその平方根になります。仮に$y$を1とすれば

\[
T= x^2 -a
\]

よってこの$T$が平方非剰余であるものを選んでその$\frac{p+1}{2}$乗を計算すればそれが答えになります。なお計算上は$x$と$y$だけが重要で$\sqrt{T}$が何ものであるかとは気にする必要がなく、$x, y$のペアでのみ演算をし$T$は二乗したら$T$となる数とゆるく考えておけば問題ありません。つまり単純に無理数の$\sqrt{T}$と考えても問題ないということになります。

例)
$p=41$とし$8$の平方根を考えます。$5^2-8=17$は非平方剰余です。よって$F_{1681}$で考えることにより
\[
(5+\sqrt{17})^{21}
\]
が答えになります。

実際計算をしてみると
\[
\begin{eqnarray}
(5+\sqrt{17})^2=(1+10\sqrt{17})\\
(5+\sqrt{17})^4=(20+20\sqrt{17})\\
(5+\sqrt{17})^8=(25+21\sqrt{17})\\
(5+\sqrt{17})^{16}=(4+25\sqrt{17})
\end{eqnarray}
\]
ですので
\[
(5+\sqrt{17})^{16}(5+\sqrt{17})^{4}(5+\sqrt{17})^{1} =34
\]

となります。

数が膨れあがらないのはその都度41で係数の剰余を取っているからです。また21回掛け合わせる必要はなく21は16+4+1ですから16乗、4乗、1乗したものを掛け合わせれば十分です。

余談）
$F_p$のような体を有限体（要素の数が有限なので）と言いますがその要素の数（位数とよぶ）は必ず$p$の冪であり、また$p$の冪の有限体は必ず存在することがわかっています。

\[
x^2=a \pmod p
\]
を求めるアルゴリズムとその原理の紹介です。アルゴリズムについては
mod pでの平方根
に書いてあるものと基本的に同じです。
任意の素数$p$に対して

\[
a^{\frac{p-1}{2}} = \pm 1\pmod p
\]

が成立しその符号は$a$が平方剰余かどうかで決まります。今回二乗して$a$になる数を探すので$a$は必ず平方剰余です。つまり上式の値は1です。この式の両辺にさらに$a$を乗ずると

\[
a^{\frac{p+1}{2}} = a\pmod p
\]

よって$\frac{p+1}{2}$が偶数なら

\[
(a^{\frac{p+1}{4}})^2 = a\pmod p
\]

よって

\[
a^{\frac{p+1}{4}}
\]
が解になります。これは$p$が$4N+3$型の素数のときに使えます。簡単ですね。

そうではないとき（つまり$p$が$4N+1$型の素数のとき）は次のように考えます。

\[
a^{\frac{p-1}{4}}=\pm 1 \pmod{p}
\]

です。ここから両辺に$a$を乗ずると

\[
a^{\frac{p+3}{4}}=\pm a \pmod{p}
\]

よって$p$が$8N+5$型の素数ならば

\[
\pm (a^{\frac{p+3}{8}})^2= a \pmod{p}
\]
符号が正の場合は$a^{\frac{p+3}{8}}$が解になります。

負の場合は$4N+1$型の素数は-1が平方剰余であるのであらかじめ$-1$の根号($x^2$=-1となる数。仮に$i$と記述する）を求めておけば $ia^{\frac{p+3}{8}}$が解になります。

$i$は平方非剰余の数を$(p-1)/4$すれば見つかります。$1\cdots p-1$なる数のうち半数が平方剰余で半数が平方非剰余ですから2から順番に探索していけば高確率ですぐ見つかりますが$8N+5$型については2が常に平方非剰余ですので$2^{(p-1)/4}$をあらかじめ計算しておけば良いことになります。

最後に残ったケース、$p$が$8N+1$型の素数についてはちょっとややこしいので次のエントリーに書きます。