DivineJK’s diary

Z cjikf c evf'

群論と離散対数のお時間です - 1

BSGSを知っていますか?私は知りません。

ということでBSGSのWikipediaを読み漁っていたら、何やらさらにつよいPohlig-Hellman's algorithmなるアルゴリズムがあるじゃないですか!ちょうどその数日前にSA-ISを実装して調子に乗っていたため、アルゴリズムがわりとシンプルじゃけん実装できるじゃろ!と思い実装したところ、世の中はそんなに甘くなく、めちゃくちゃバグり散らしました。世の中ってどうしたら甘くなるんでしょうね。この世界に真っ赤なジャムでも塗れば良いんでしょうか。ところで私ははちみつ派です。おすすめのはちみつがあればご一報ください。

さて、このアルゴリズムですが、なにやら群論の知識をたくさん使うらしいので、メモ化再帰的にわかるところまで進んでから一つずつ回収していく、という手法で理解しようと思いました。また、一応私は大学での専攻が物理学で、世の中の99.7%くらいの人には理解されないので詳細は省きますが、群論など抽象的な代数学を多用する分野に興味があるので、まとめてやっちゃおう、という勢いでやってます。個人用のメモでも良かったんですが、世の中には私と同じようにBSGSを一般化したい人がいるかもしれないと思い、公開します。

材料としてはおもに昔受けた群論に関する講義での手書きの講義ノートです。このこともデジタルな文書として残しておきたい理由で、私のページをケチる癖でよくわからないことになっている部分があるのと、後で見返したときにページ内検索ができるためです。この記事を読んでいる若い学生さんはちゃんと整理整頓されたわかりやすいノートを書きましょうね。

目標

  • ラグランジュの定理についてやる。
  • Pohlig-Hellman's algorithm を実装する。

基本

定義がいっぱいです。

群の公理

群の公理は以下のようなものです。 Gを群とし、 Gの元 x, yの積を単に xyと書くことにします。

  1. 演算が閉じている。 \forall x, y \in G; xy \in G
  2. 結合則が成り立つ。 \forall x, y, z \in G; x(yz) = (xy)z
  3. 単位元が存在する。 \exists e\in G \,\, \mathrm{s.t.}\,\,\forall x\in G; ex = xe = x
  4. 逆元が存在する。 \forall a\in G\, \exists b\in G\,\,\mathrm{s.t.}\,\, ab = ba = e

群の一例として、整数の集合に群の演算として足し算の構造を入れたものがあります(どの隣り合う二つの数の足し算から実行しても結果は同じで、単位元0と整数 aに対する逆元 -aがあります)。また、1.と2.のみを満たすものを半群、1.と2.と3.のみを満たすものをモノイドといいます。モノイドはセグ木に乗ることでよく知られていますね。 n\times n行列の集合に積の演算を入れたものはモノイドの一例です。

部分群

 Gの部分集合 Hであって、 Gの演算で群のとき、 H Gの部分群であるといいます。

群の生成系

 Gの部分集合 Sであって、 Gからいくつか(無限個でもよい)元をとってきたものを考えます。つまり、 S = \{ g_1, g_2, \cdots \} (g_i\in G)です。 Sの生成する Gの部分群とは、この集合の(重複を許して)有限個の元およびその逆元の積全体からなる集合、すなわち、 nを選んだ元の個数として、 g_1^{\pm 1}g_2^{\pm 1}\cdots g_n^{\pm 1}がなす集合です。この集合は、 \langle S\rangleと書かれます。

すこし説明が難しいので例を考えます。 S = \{2, 3\}とすると、 \mathrm{gcd}(2, 3) = 1であるので任意の整数 nについて 2x + 3y = nを満たす整数 x, yが存在します。よって、 S \mathbb{Z}を生成します。ここで、 4 = 2 + 2のように、同じ元を複数回選んでも良いです。

巡回群

一つの元 g\in Gから生成される群 \langle g\rangle巡回群とよばれます。そして、もし  g^{m} = e となるような最小の自然数 mが存在するなら、この m位数といい、 \langle g\rangleは位数 mの有限巡回群といいます。存在しなければ無限巡回群と呼ばれます。

有限巡回群の例として、 \mathrm{mod}\, m上での足し算があります。 1 m個足していくと単位元 0になります。

群準同型

 f: G\rightarrow G'写像を考えます。例によって G, G'は群です。そして、 \forall g_1, g_2\in Gに対し f(g_1g_2) = f(g_1)f(g_2)となるとき、 f準同型写像であるといい、このような写像が存在すれば G G'群準同型であるとします。

準同型写像というのはどういうものかを説明します。もともと群には二項演算が入っています。これは、 g_1, g_2\in Gに対し g_1g_2\in Gという群の要素を定めるので、この二項演算は G\times G \rightarrow Gです。さらに、写像 fによってこの要素を写すと、 f: G\rightarrow G'なので f(g_1g_2)\in G'です。つまり、 Gの二つの要素に対して二項演算をしてから写像 f G'に写す、という操作です。この操作はまとめると G\times G\rightarrow G'です。

一方、 Gの要素を写像で写してからそれらの二項演算を行っても G\times G\rightarrow G'となります。このとき、 g_1, g_2\in Gに対し f(g_1)f(g_2)\in G'となります。つまり、 f準同型写像であれば、この2通りの結果が等しいということなのです。

さらに、この写像全単射であれば、 f同型写像、または、 G G'同型であるといい、 G\simeq G'と表されます。

同値類

集合 Aについて R: A\times A\rightarrow \{0, 1\}というような関係を二項関係といい、 a, b, c\in Aに対して以下の3つを満たす二項関係 Rを同値関係といいます。

  1.  a\,R\,a (反射律)
  2.  a\,R\,b\, \Rightarrow b\,R\,a (対称律)
  3.  a\,R\,b \wedge b\,R\,c\Rightarrow a\,R\,c (推移律)

例えば等号の =はこの条件を満たします。意味的にはもっと広く、「 a bがある基準を以って仲間ですか」という質問にYesであれば同値、Noであれば同値ではない、という感じです。以降、同値関係は \simで表します。

そして、集合 Aに対して、 [x] = \{y\in A | x\sim y \}と定義します。この [x]は、 xと同値な Aの要素の集合で、同値類と呼ばれます。そして、 [x]からなる集合 \{[x]|x\in A\} Aに対する商集合といい、 A/\simと表します。

剰余類

 Gを群として、 H Gの部分群とします。そして、 Gの元 g, g'に対し、 g^{-1}g'\in H\Rightarrow g\sim g'であるとします。この二項関係が同値なことは非自明ですが、がんばって説明してください。そしてあなたが大嫌いな人に高らかに自慢しましょう。

ここで、 [ g]がどういう集合かを考えてみたいと思います。

まず、 g^{-1}g'\in H \Rightarrow \exists h\in H\, \mathrm{s.t.}\, g^{-1}g' = h \Rightarrow g' = ghとなります。同値類 [g]の定義は、 gと同値なものの集合という定義でした。 g' [g]の要素であるので、 [g] = \{g, gh_1, \cdots\}であることがわかります。これは、 Hの各要素の左から gをかけたものを集めたもの、と解釈できます。そして、この [g] gHと表し、 gHを要素とした商集合は G/H = \{gH|g\in G\}と書かれ、左剰余類と呼びます。右剰余類も似たように定義できます。 G/Hの要素数は、 Gにおける Hの指数、といいます。

例として、 [0, 28)の整数の集合に \bmod 28の足し算の構造を入れたものを考えます。これは群であることがわかると思います。この部分群として、集合 \{0, 7, 14, 28\} \bmod 28の足し算の構造を入れたものを考えられます。すると、 [i] = \{i+h|h\in \{0, 7, 14, 28\}\}(0\le i\le 6)として、左剰余類は \{[0], [1], [2], [3], [4], [5], [6]\}です。

ところで、 g_i, g_j\in Gという二つの元が同値でなかったとき、 [g_i], [g_j]の関係性はどうなるでしょうか。1300234241で割ったあまりを求めてください。具体的には、この二つの集合の共通部分はどうなるでしょう。そこで、 [g_i], [g_j]が共通部分をもつ、つまり、 h_k, h_l\in Hについて g_ih_k = g_jh_lなる要素があると仮定します。 h_lは部分群の要素なので、 Hに逆元を持ちます。よって g_ih_kh_l^{-1} = g_jです。そして、 h_kh_l^{-1}という積はハンターハンターなので H\times Hなので、 Hのある元です。この元を h_kh_l^{-1} = h\in Hとおくと、 g_j = g_ihですので、 g_i^{-1}g_j\in Hです。 g_i^{-1}g_j\in H\Rightarrow g_i\sim g_jですが、これは g_i, g_jが同値でないという仮定に反します。よって、 [g_i], [g_j]は共通部分をもちません。

ラグランジュの定理

一応、準備は整ったので、本題のひとつ「ラグランジュの定理」の証明と応用に移ります。

定理の内容

 Gを有限群とし、 H Gの部分群としたときに、 Hの位数は Gの位数の約数である。より具体的には、 Gの位数は G/Hの要素数 Gにおける Hの指数)と Hの位数を掛け合わせたものである。

証明

 g\in Gとします。 Hの位数を mとして、 H = \{h_1, h_2, \cdots, h_m\}とします。すると、左剰余類 gH = \{gh_1, gh_2, \cdots, gh_m\}です。また、 f: H\rightarrow gH f(h) = gh\, (h\in H)という写像とします。

まず、任意の1\le i, j\le m h_i, h_j\in Hについて f(h_i) = f(h_j) \Leftrightarrow gh_i = gh_jであれば、両辺に g^{-1}を作用させることで h_i = h_jが言えるため、 f単射です。

加えて、 gH Hの要素に左から gをかけて作った集合なので、 f(h)=gh\in gH\Rightarrow \exists h\in Hであるはずです(そうでなければ私が病み散らかしてしまいます)。よって、 f全射です。

以上より、f全単射であることがわかりました。よって H gHが同型であることから、 gHの要素数 mです。

さて、 Gの互いに同値でないものを集めた集合を、要素数 kとして \{a_1, a_2, \cdots a_k\}とします。 Hとはそもそも Gの部分集合ですから、 a_iHのどの元も Gに含まれています。そして、類別を行うときに全ての元の対で同値関係を決めたため、 Gの元であってどの a_iHにも含まれていないものはありません。つまり、 Gのどの元もa_iHのどこかに属しています。したがって、 G =  a_1H \cup a_2H\cup\cdots \cup a_kHです。

また、先に示したように、任意の iについて a_iHの要素数 mです。さらに、剰余類のところで見たように、任意の 1\le i, j\le k, i\neq jについて a_iH\cap a_jH = \emptysetです。 Gの位数は包除原理を用いるまでもなくただそれぞれの剰余類の要素数を足し合わせれば良いです。

以上より、 Gの位数は kmであるので、定理は示されました。

応用

では、ラグランジュの定理を利用して何ができるかをみていきたいと思います。

巡回群について

 g\in Gが生成する巡回群 \langle g\rangle Gの部分群です。これにラグランジュの定理を適用すると、 \langle g\rangleの位数は Gの位数の約数であることが言えます。このことから、 g^{| \langle g\rangle|}=eより g^{|G|} = eです。

フェルマーの小定理

フェルマーの小定理とは、素数 pと、 pと互いに素な整数 aについて、 a^{p-1}\equiv 1\bmod pであるというものです。二項定理を用いた証明が簡単ですが、ラグランジュの定理を用いても示せます。

 p素数であることから 1, 2, \cdots, p-1のすべての数は pと互いに素です。このことは、 \bmod pでの逆元の存在を保証します。 [i]を、 iを含む剰余類とすると、 pの倍数を除いた集合は \bmod p上の積で群となり、 \{[1], [2], [3], \cdots, [p-1]\}と類別されます。この位数は p-1なので、 a^{p-1}\equiv 1\bmod p\,(1\le a\le p-1, m\in \mathbb{Z})です。

フェルマーの小定理はよく知られているようにさらに一般化できます。一般の2以上の整数 nと、 nと互いに素な整数 aについて、 n以下の正の整数で nと互いに素なものの個数 \varphi(n)を用いて a^{\varphi(n)}\equiv 1\bmod nです。これも同じようにラグランジュの定理を用いて示せます。ただし、今度は n未満の正の整数で nと互いに素ではないものがあるかもしれないので、それを除いた剰余類で群を作らなくてはなりません。これが指数の \varphi(n)の由来です。

小休止

あー疲れた。群論つら。ちなみにこの記事をここまで書くのに3~4日くらいかかりました。

ところでおすすめの原宿系ファッションのお店の情報は随時お待ちしております。どんな方法でも情報送ってくれたら僕が喜びます。

離散対数

問題

正の整数 Mと、 0以上 M-1以下の整数 X, Yが与えられる。 X^{K}\equiv Y\bmod Mを満たす最小の非負整数 Kが存在すればそれを求め、存在しなければその旨を報告せよ。 (1\le M\le 10^{9})

Baby-step giant-step(BSGS)

 \bmod M Xに逆元があるとき、すなわち、 X Mが互いに素のときは、baby-step giant-step(略してBSGS)というアルゴリズムが使用できます。

 M Xが互いに素であれば、剰余類 [X]フェルマーの小定理の証明に出てきた群の要素です。よって、問題の等式を満たす Kが存在するなら、それは \varphi(M)-1以下の非負整数のどれかです。しかし、 1\le M\le 10^{9}なので、まともに全探索したら間に合いません(無理矢理高速化したりするとコンピュータが泣いてショートしてしまいます)。

そこで、 m = \lceil \sqrt{\varphi(M)}\rceilとして、 K = im + j\, (0\le i, j \le m-1)とおいてみます。すると、問題の等式はX^{im+j}\equiv Y \Leftrightarrow X^{j}\equiv Y(X^{-m})^{i}と変形できます。ここで、 X Mが互いに素であることから、 Xに逆元が存在することを使いました。

ここで、あらかじめ 0\le j\le m-1について v \equiv X^{j}となるような最小の jを求めておくことで、もし v \equiv Y(X^{-m})^{i}なる jが存在すれば im+jが答えになります。ちょっとわかりにくいですが、以下に示す実装の手順を見ればわかると思います。


【実装の手順】

入力: X, Y, M

出力: K(等式 X^{K}\equiv Y\bmod Mを満たす最小の非負整数、存在しなければ -1

  1.  m = \lceil \sqrt{M}\rceilを求める。
  2.  b = X^{-m}とする。
  3. 辞書などを用いて 0\le j\le m-1について組 (X^{j}, j)を持っておく。
  4.  0\le i\le m-1について、 X^{j}=(Yb)^{i}なる jが存在すれば im+jを返して終了。
  5. 終了しなければ、 -1を返して終了。

実装上の注意点として、辞書に値を格納するときに同じkeyに対して異なる jが複数対応することがあり、そのとき jの昇順のループでは jの最大値で更新されてしまいます。 jの降順でループするか、すでにkeyが辞書に入っているときは値の更新をしない、などの方法で対応できます。

時間計算量、空間計算量ともに \mathrm{O}(\sqrt{M})です。

お知らせ

すみません、ここにPohlig-Hellman algorithmの解説を書く予定でしたが、ちょっと想定より長くなったので次回の自分に投げます。次回は

  • Pohlig-Hellman algorithm
  • 一般modでの離散対数の考察

について書く予定です。余裕があれば具体的な実装を書く予定ですが、分量が多くなればまた次回以降に回します。