baby-step giant-step - sigma425のブログ

${x^k = y\pmod{z}}$ なるmin kを(あるなら)求めよ、という問題

解き方:
とりあえずzを素数とします.
自然数Hを適当に取り、kをaH-bと書く(1<=a,0<=b<=H-1).
${x^{aH-b} = y\pmod{z}}$ の両辺に ${x^b}$ をかけ、
${x^{aH} = x^by \pmod{z}}$
今zが素数なので ${x^{-1}}$ が存在して、上と下は同値になる.よって下のようなaとbを求めれば良い.mod zでの値はz個くらいしか無いので周期は高々zなのでaはz/Hくらいまで調べれば良い.まず ${x^by}$ を順番に計算しておき,indexとペアにしてソートしておきます.baby stepという.O(HlogH)
その後,x^aHを計算していきます.この時,この計算結果と一致するものがあるかsetから調べます.こっちがgiant step.O(z/H*logH)
この時H= ${\sqrt{z}}$ くらいにすると、全体で ${O(\sqrt zlogz)}$ 位になるのでいい感じ.
細かいところでは、x^aHと一致するbが複数あった場合:これはそもそも周期がH未満になっているのでbaby stepの方で計算して一致するか確かめると良い.

zが素数でない場合:実はunderlineの条件はもうちょっと弱められて,逆元が存在するためにはxとzが互いに素であることが必要十分なので,互いに素ならさっきみたいに解ける.互いに素でない場合
${p\mid z}$ なるpを一つ取る.
${p\mid x}$ xor ${p\mid k}$ が真の時はNo solutionなのはわかる.(zの素因数をとっているので,nxtをとる( ${x^k}$ から ${x^{k+1}}$ を計算することをここではこう書きます)時に素因数pはあるなら残り続けて,(xに)ないなら新たに現れたりはしません)
そうでない時でも,例えば ${2^k = 12\pmod{40}}$ みたいに,k<=2では成立しなくて,k>3になると2^kが8の倍数になってしまい12とは一致しない,みたいなことが起こります.
zの素因数毎にわざわざこういう場合分けをするのはさすがに面倒ですが,うまい方法があって,とりあえず何回かnxtをとるとよいです.(その間にkと一致したらその答えを返します)
十分にnxtを回した時, ${x^k \bmod z}$ とzとのgcdをg1とおき,gcd(z,k)をg2とおくと,g1とg2は(解があるためには)一致する必要があります.
理由:g1には,gcd(z,x)にあらわれていた素因数のめいっぱいのオーダー(つまりord_p(z)←zをpが何回割り切るか)分まで含んでいます(というか含むまで回します,少なくともlog_2(z)回回せば十分ですね).なのでこの時点で ${g1\nmid g2}$ ならもう絶対にg1に含まれる素因数はx^kには出てこないので,不可能になります.また ${g2\nmid g1}$ でも,"通り過ぎちゃってる"(さっきの ${2^k = 12\pmod{40}}$ の例)のでもう一致することはありません.

で、ここまでやって何が嬉しいかというと,g(=g1=g2のこと)とz/gが互いに素ですね?(gに含まれる素数pはord_p(g)=ord_p(z)をみたすので)つまり中国剰余定理が使えます.
mod gの方はもはや成り立つのが自明です(両辺0)
mod z/gの方では, ${x^k \pmod z}$ とz/gは互いに素(さっきと同じ理由)なので,元の簡単なパターンに帰着できました.解けます.

ちょっと雑だけど自分用なのでゆるして