読者です 読者をやめる 読者になる 読者になる

baby-step giant-step part2

part1→一般的な話をします.
さっきの議論でこのアルゴリズムを使える条件は,
・なんか演算gがあって,元の値aからg(a)がとれる(さっきのだと,g(a)=a*x%mod z)
・その演算gは結合法則が成り立つ(g^nとか書ける)
・gを0回したものはさすがに恒等写像であってほしい
・gを打ち消す操作(gの逆元)があるべき(さっきのだとxとzが互いに素であることと同値)
どうみても群の作用ですね.
解ける問題の形はこう:
群Gの集合Xへの作用を考える.g∈G,s,t∈Xとする.gは有限位数.g^n(s)=tとなる最小のnを求めよ.(群Gの作用じゃなくてgが生成する部分群だけでいいけどまあ細かいことはアレ)

解き方はほぼ同じで,n=aH-bと置く.g^{aH}(s)=g^{b}(t)と同値.g^{b}(t)を計算しておく.g^{aH}(s)を順番に計算していき,結果を探す.

一つ計算量に関する注意点があって,"作用同士のG上の演算にかかる計算"と"Xの要素に作用させるときの計算"の2種類があり,計算量が変わってくる(part1の例だと両方かけ算とmodだけだったが,例えばGをあるN*N行列(要素はZ/mZ),Xをベクトルとかにすると,作用同士は(愚直で)O(N^3),作用を行う計算はO(N^2)になる.だから,それぞれのstepで毎回作用を求めてから集合の要素に作用させる計算をさせてると遅くなりうるので,やめましょう(ただし,g^Hは求めなければいけないことに注意(exを使おう)).

で,問題は,問題によってgの逆元がないことがある事で,こうなるとモノイドの作用にランクダウン?します.一般になんか初めに何回かくるくる回したりすると行けるかどうか分かったりしないかなあ(妄想).まあ恐らくそういう問題が出た時は初めに何回かくるくる回せば逆元がある場合に帰着できるようなのしか出ない(そうじゃないと(自分の頭が理解できる範囲では)解けない)と思うので,まあ各問題に対して逆元が存在する条件を考えましょう.


この記事に比べてpart1読みにくすぎるし要らなかったのでは

(妄想の追加)
Gをちゃんとgが生成する部分群に置き直す.集合Xの要素x,yに対し,g(x)=yならxからyに辺を張ったようなグラフを考える.g^{-1}があればグラフは逆向きにも使えるので軌道による類別を考えることが出来るけど,そうでない時は(...)