群論と離散対数のお時間です - 1
BSGSを知っていますか?私は知りません。
ということでBSGSのWikipediaを読み漁っていたら、何やらさらにつよいPohlig-Hellman's algorithmなるアルゴリズムがあるじゃないですか!ちょうどその数日前にSA-ISを実装して調子に乗っていたため、アルゴリズムがわりとシンプルじゃけん実装できるじゃろ!と思い実装したところ、世の中はそんなに甘くなく、めちゃくちゃバグり散らしました。世の中ってどうしたら甘くなるんでしょうね。この世界に真っ赤なジャムでも塗れば良いんでしょうか。ところで私ははちみつ派です。おすすめのはちみつがあればご一報ください。
さて、このアルゴリズムですが、なにやら群論の知識をたくさん使うらしいので、メモ化再帰的にわかるところまで進んでから一つずつ回収していく、という手法で理解しようと思いました。また、一応私は大学での専攻が物理学で、世の中の99.7%くらいの人には理解されないので詳細は省きますが、群論など抽象的な代数学を多用する分野に興味があるので、まとめてやっちゃおう、という勢いでやってます。個人用のメモでも良かったんですが、世の中には私と同じようにBSGSを一般化したい人がいるかもしれないと思い、公開します。
材料としてはおもに昔受けた群論に関する講義での手書きの講義ノートです。このこともデジタルな文書として残しておきたい理由で、私のページをケチる癖でよくわからないことになっている部分があるのと、後で見返したときにページ内検索ができるためです。この記事を読んでいる若い学生さんはちゃんと整理整頓されたわかりやすいノートを書きましょうね。
目標
- ラグランジュの定理についてやる。
- Pohlig-Hellman's algorithm を実装する。
基本
定義がいっぱいです。
群の公理
群の公理は以下のようなものです。を群とし、の元の積を単にと書くことにします。
群の一例として、整数の集合に群の演算として足し算の構造を入れたものがあります(どの隣り合う二つの数の足し算から実行しても結果は同じで、単位元0と整数に対する逆元があります)。また、1.と2.のみを満たすものを半群、1.と2.と3.のみを満たすものをモノイドといいます。モノイドはセグ木に乗ることでよく知られていますね。行列の集合に積の演算を入れたものはモノイドの一例です。
部分群
群の部分集合であって、の演算で群のとき、はの部分群であるといいます。
群の生成系
群の部分集合であって、からいくつか(無限個でもよい)元をとってきたものを考えます。つまり、です。の生成するの部分群とは、この集合の(重複を許して)有限個の元およびその逆元の積全体からなる集合、すなわち、を選んだ元の個数として、がなす集合です。この集合は、と書かれます。
すこし説明が難しいので例を考えます。とすると、であるので任意の整数についてを満たす整数が存在します。よって、はを生成します。ここで、のように、同じ元を複数回選んでも良いです。
巡回群
一つの元から生成される群は巡回群とよばれます。そして、もし となるような最小の自然数が存在するなら、このを位数といい、は位数の有限巡回群といいます。存在しなければ無限巡回群と呼ばれます。
有限巡回群の例として、上での足し算があります。を個足していくと単位元になります。
群準同型
な写像を考えます。例によっては群です。そして、に対しとなるとき、は準同型写像であるといい、このような写像が存在すればとは群準同型であるとします。
準同型写像というのはどういうものかを説明します。もともと群には二項演算が入っています。これは、に対しという群の要素を定めるので、この二項演算はです。さらに、写像によってこの要素を写すと、なのでです。つまり、の二つの要素に対して二項演算をしてから写像でに写す、という操作です。この操作はまとめるとです。
一方、の要素を写像で写してからそれらの二項演算を行ってもとなります。このとき、に対しとなります。つまり、が準同型写像であれば、この2通りの結果が等しいということなのです。
さらに、この写像が全単射であれば、は同型写像、または、とが同型であるといい、と表されます。
同値類
集合についてというような関係を二項関係といい、に対して以下の3つを満たす二項関係を同値関係といいます。
- (反射律)
- (対称律)
- (推移律)
例えば等号のはこの条件を満たします。意味的にはもっと広く、「とがある基準を以って仲間ですか」という質問にYesであれば同値、Noであれば同値ではない、という感じです。以降、同値関係はで表します。
そして、集合に対して、と定義します。このは、と同値なの要素の集合で、同値類と呼ばれます。そして、からなる集合をに対する商集合といい、と表します。
剰余類
を群として、をの部分群とします。そして、の元に対し、であるとします。この二項関係が同値なことは非自明ですが、がんばって説明してください。そしてあなたが大嫌いな人に高らかに自慢しましょう。
ここで、がどういう集合かを考えてみたいと思います。
まず、となります。同値類の定義は、と同値なものの集合という定義でした。はの要素であるので、であることがわかります。これは、の各要素の左からをかけたものを集めたもの、と解釈できます。そして、このをと表し、を要素とした商集合はと書かれ、左剰余類と呼びます。右剰余類も似たように定義できます。の要素数は、におけるの指数、といいます。
例として、の整数の集合にの足し算の構造を入れたものを考えます。これは群であることがわかると思います。この部分群として、集合にの足し算の構造を入れたものを考えられます。すると、として、左剰余類はです。
ところで、という二つの元が同値でなかったとき、の関係性はどうなるでしょうか。1300234241で割ったあまりを求めてください。具体的には、この二つの集合の共通部分はどうなるでしょう。そこで、が共通部分をもつ、つまり、についてなる要素があると仮定します。は部分群の要素なので、に逆元を持ちます。よってです。そして、という積はハンターハンターなのでなので、のある元です。この元をとおくと、ですので、です。ですが、これはが同値でないという仮定に反します。よって、は共通部分をもちません。
ラグランジュの定理
一応、準備は整ったので、本題のひとつ「ラグランジュの定理」の証明と応用に移ります。
定理の内容
を有限群とし、をの部分群としたときに、の位数はの位数の約数である。より具体的には、の位数はの要素数(におけるの指数)との位数を掛け合わせたものである。
証明
とします。の位数をとして、とします。すると、左剰余類です。また、をという写像とします。
まず、任意ののについてであれば、両辺にを作用させることでが言えるため、は単射です。
加えて、はの要素に左からをかけて作った集合なので、であるはずです(そうでなければ私が病み散らかしてしまいます)。よって、は全射です。
以上より、が全単射であることがわかりました。よってとが同型であることから、の要素数はです。
さて、の互いに同値でないものを集めた集合を、要素数をとしてとします。とはそもそもの部分集合ですから、のどの元もに含まれています。そして、類別を行うときに全ての元の対で同値関係を決めたため、の元であってどのにも含まれていないものはありません。つまり、のどの元ものどこかに属しています。したがって、 = です。
また、先に示したように、任意のについての要素数はです。さらに、剰余類のところで見たように、任意のについてです。の位数は包除原理を用いるまでもなくただそれぞれの剰余類の要素数を足し合わせれば良いです。
以上より、の位数はであるので、定理は示されました。
応用
では、ラグランジュの定理を利用して何ができるかをみていきたいと思います。
巡回群について
が生成する巡回群はの部分群です。これにラグランジュの定理を適用すると、の位数はの位数の約数であることが言えます。このことから、よりです。
フェルマーの小定理
フェルマーの小定理とは、素数と、と互いに素な整数について、であるというものです。二項定理を用いた証明が簡単ですが、ラグランジュの定理を用いても示せます。
が素数であることからのすべての数はと互いに素です。このことは、での逆元の存在を保証します。を、を含む剰余類とすると、の倍数を除いた集合は上の積で群となり、と類別されます。この位数はなので、です。
フェルマーの小定理はよく知られているようにさらに一般化できます。一般の以上の整数と、と互いに素な整数について、以下の正の整数でと互いに素なものの個数を用いてです。これも同じようにラグランジュの定理を用いて示せます。ただし、今度は未満の正の整数でと互いに素ではないものがあるかもしれないので、それを除いた剰余類で群を作らなくてはなりません。これが指数のの由来です。
小休止
あー疲れた。群論つら。ちなみにこの記事をここまで書くのに3~4日くらいかかりました。
ところでおすすめの原宿系ファッションのお店の情報は随時お待ちしております。どんな方法でも情報送ってくれたら僕が喜びます。
離散対数
問題
正の整数と、以上以下の整数が与えられる。を満たす最小の非負整数が存在すればそれを求め、存在しなければその旨を報告せよ。
Baby-step giant-step(BSGS)
でに逆元があるとき、すなわち、とが互いに素のときは、baby-step giant-step(略してBSGS)というアルゴリズムが使用できます。
とが互いに素であれば、剰余類はフェルマーの小定理の証明に出てきた群の要素です。よって、問題の等式を満たすが存在するなら、それは以下の非負整数のどれかです。しかし、なので、まともに全探索したら間に合いません(無理矢理高速化したりするとコンピュータが泣いてショートしてしまいます)。
そこで、として、とおいてみます。すると、問題の等式はと変形できます。ここで、とが互いに素であることから、に逆元が存在することを使いました。
ここで、あらかじめについてとなるような最小のを求めておくことで、もしなるが存在すればが答えになります。ちょっとわかりにくいですが、以下に示す実装の手順を見ればわかると思います。
【実装の手順】
入力:
出力:(等式を満たす最小の非負整数、存在しなければ)
- を求める。
- とする。
- 辞書などを用いてについて組を持っておく。
- について、なるが存在すればを返して終了。
- 終了しなければ、を返して終了。
実装上の注意点として、辞書に値を格納するときに同じkeyに対して異なるが複数対応することがあり、そのときの昇順のループではの最大値で更新されてしまいます。の降順でループするか、すでにkeyが辞書に入っているときは値の更新をしない、などの方法で対応できます。
時間計算量、空間計算量ともにです。
お知らせ
すみません、ここにPohlig-Hellman algorithmの解説を書く予定でしたが、ちょっと想定より長くなったので次回の自分に投げます。次回は
- Pohlig-Hellman algorithm
- 一般modでの離散対数の考察
について書く予定です。余裕があれば具体的な実装を書く予定ですが、分量が多くなればまた次回以降に回します。