modに対するアプローチ

Latest Author 37zigen37zigen /Date 2020-01-09 13:33:37 / Views 4884
3 (Favした一覧ページはユーザーページから)
分解してみる
例題: nCk(mod20){}_n \mathrm{C} _k \pmod{20} を求めよ。 ただし 0kn1060\leq k \leq n \leq 10^{6}
nCkn(n1)(n2)(nk+1)k!(mod20){}_n \mathrm{C} _k \equiv \frac{n (n-1) (n-2) \ldots (n-k+1)}{k!} \pmod{20} なので {k!}1(mod20)\{k!\}^{-1} \pmod{20} が計算できればよさそうですが
k!k!2020 が互いに素になるかはわかりません。仮に互いに素でない場合は逆元が存在しないのでこのままでは解けません。
そこで 20=22×520 = 2^{2} \times 5 であることに着目して
  • n(n1)(n2)(nk+1)=2t1×5f1×r1n (n-1) (n-2) \ldots (n-k+1) = 2^{t_1}\times 5^{f_1}\times r_{1}
  • k!=2t2×5f2×r2k! = 2^{t_2}\times 5^{f_2}\times r_{2}
と分解してみます。すると答えは 2t1t2×5f1f2×r1×r21(mod20)2^{t_1 - t_2}\times 5^{f_1 - f_2}\times r_1 \times {r_2}^{-1} \pmod{20} になります。
いま r2r_{2}2255 は含まれていないので r2r_{2}2020 が必ず互いに素になり逆元が計算できます。
中国人剰余定理
m1,m2mkm_{1}, m_{2} \ldots m_{k} がどの2つも互いに素ならば
  • xa1(modm1)x \equiv a_{1} \pmod{m_{1}}
  • xa2(modm2)x \equiv a_{2} \pmod{m_{2}}
  • \ldots
  • xak(modmk)x \equiv a_{k} \pmod{m_{k}}
をすべて満たす xxm1m2mkm_{1} m_{2} \ldots m_{k} を法として一意に存在する」というのが中国人剰余定理です。

f(n)(modm)f(n) \pmod m を直接計算するのは難しい・大変である場合でも、m=p1e1p2e2...pkekm = {p_1}^{e_1} {p_2}^{e_2} ... {p_k}^{e_k} と分解して
  • f(n)r1(modp1e1) f(n) \equiv r_1 \pmod{{p_1}^{e_1}}
  • f(n)r2(modp2e2) f(n) \equiv r_2 \pmod{{p_2}^{e_2}}
  • \ldots
  • f(n)rk(modpkek) f(n) \equiv r_k \pmod{{p_k}^{e_k}}
を計算できたのであればそれらから f(n)(modm)f(n) \pmod m を計算することができます。

上の問題でいうと nCk(mod22){}_n \mathrm{C} _k \pmod{2^{2}}nCk(mod5){}_n \mathrm{C} _k \pmod{5} が計算できれば nCk(mod20){}_n \mathrm{C} _k \pmod{20} を計算できることになります。
詳細は割愛しますが nCk(modpe){}_n \mathrm{C} _k \pmod{p^e} は前処理に O(pe)O(p^e) かけることで一回あたり O(logn)O(\log n) で計算することができます。
逆元を消してみる
  • f(n,p):=n!f(n, p) := n! のなかに素数 pp が何個含まれているか
上記を定義しておくと nCk2f(n,2)f(k,2)f(nk,2)×3f(n,3)f(k,3)f(nk,3)(mod20){}_n \mathrm{C} _k \equiv 2^{f(n,2)-f(k,2)-f(n-k,2)} \times 3^{f(n,3)-f(k,3)-f(n-k,3)} \ldots \pmod{20} となります。
こうすると逆元というやっかいな操作を気にする必要がなくなります。
逆元を使った小ネタ
いま 2322^{32} と互いに素な b<232b < 2^{32} を考えてみます。 互いに素なので当然 b1(mod232)b^{-1} \pmod{2^{32}} が計算できます。
ここで 2322^{32} 未満の bb の倍数を考えてみると 0, b, 2b2321bb0,\ b,\ 2b \ldots \lfloor \frac{2^{32}-1}{b} \rfloor b があります。これらに b1(mod232)b^{-1} \pmod{2^{32}} を掛け 2322^{32} で余りを取ると 0,1,22321b0, 1, 2 \ldots \lfloor \frac{2^{32}-1}{b} \rfloor になります。
また n≢m(mod232)nb1≢mb1(mod232)n \not\equiv m \pmod{2^{32}} \Rightarrow nb^{-1} \not\equiv mb^{-1} \pmod{2^{32}} であるので 2322^{32}未満で bb の倍数でないものに b1(mod232)b^{-1} \pmod{2^{32}} を掛け 2322^{32} で余りを取ると 2321b\lfloor \frac{2^{32}-1}{b} \rfloor より大きくなります。
つまりこれを使うと掛け算のみで倍数判定を行うことができます。(C++のunsignedではオーバーフローすると0に巻き戻されるので余りを取るのと同じことになります。)
// 2^32未満で3の倍数かどうか判定する
bool is_3k(unsigned n){
  return n * 2863311531u <= 1431655765u;
}
離散対数問題
Pohlig–Hellman algorithmを用いて離散対数問題ax=bmodpea^x = b \bmod p^eO(ep)O(\sqrt{ep})で解ける。 まずaxbmodpa^x\equiv b\bmod pをbaby-step giant-step(BSGS)で求める。 次にα:=aa mod p,β:=bb mod p\alpha:=\frac{a}{a\ \bmod\ p},\beta:=\frac{b}{b\ \bmod\ p}として、αxβmodpe\alpha^x\equiv \beta\bmod p^eを満たすxxを求める。 αβ1modp\alpha\equiv\beta\equiv1\bmod pだからg:=(1+p)g:=(1+p)としてα,β\alpha,\betaggを生成元とする位数pe1p^{e-1}の巡回群の元。 従って、α,β\alpha,\betaggによる表示を求められると、αxβmodpe\alpha^x\equiv \beta \bmod p^eも解ける。 ここではα,β\alpha,\betahhと置いて、gxhmodpeg^x\equiv h\bmod p^eを解こう。 hxk,βh^{x_k},\betaggのべき乗で表したときのべき指数がpp進数で11桁目からkk桁目まで一致するとする。 すると、hgxkhg^{-x_k}はべき指数がkk桁目まで打ち消されるので位数pe1kp^{e-1-k}以下になる。 つまり(hgxk)pe2k(hg^{-x_k})^{p^{e-2-k}}は位数11またはppとなり、γ:=gpe2\gamma:=g^{p^{e-2}}としてγ\langle \gamma \rangleの元となる(なぜなら、γp=1\gamma^p=1よりγ\langle\gamma\rangleの位数はppであるから)。 よって、(hgxk)pe2k(hg^{-x_k})^{p^{e-2-k}}γ\gammaのべき乗による表示γdk=(hgxk)pe2k\gamma^{d_k}=(hg^{-x_k})^{p^{e-2-k}}がBSGSによって得られる。 γ:=gpe2\gamma:=g^{p^{e-2}}を戻してpdkpk=hgxkp^{d_kp^k}=hg^{-x_k}だからxk+1:=xk+pkdkx_{k+1}:=x_k+p^kd_kとなる。 通常のBSGSではx=up+vx=u\sqrt{p}+vとして0u[p]0\leq u\leq [\sqrt p]を探索するが、このアルゴリズムではγ\gammakkによらないことからx=uep+vx=u\sqrt{ep}+vとするとよい。テーブルの構築に(ep)(\sqrt{ep})かかるが、一回のBSGSの実行で見るuuの範囲がO(pe)O(\sqrt{\frac{p}{e}})となるため全体の計算量もO(ep)O(\sqrt{ep})になる。
離散対数問題(2): index calculus algorithm
離散対数問題ax=bmodpa^x=b \bmod pは平均O(e(3/2+o(1))logploglogp)O(e^{(3/\sqrt{2}+o(1))\sqrt{\log{p}\log\log{p}}})で解ける。
①小さい方から素数をkk個列挙してp1,,pkp_1,\ldots,p_kと置く。 ランダムな数hhについて計算して、p1,,pkp_1,\ldots,p_kのみを素因数に持つ(ahmodp)(a^h \bmod p)を探す(pkp_k-smoothという)。
②そのようなan=i=1kpieimodpa^n=\sum_{i=1}^k p_i^{e_i} \bmod pの指数部比較で h=i=1keilogapimod(p1)h=\sum_{i=1}^k e_i \log_{a} p_i \bmod (p-1) を得る。ord(a)(p1)\mathrm{ord}(a)|(p-1)であるからmod  p1\mod p-1を取っている。 ここで、logap1,,logapk\log_{a}p_1,\ldots,\log_{a}p_kは未知数である。
③同じような方程式を4k4k個用意する。
③そのうちkk個が線形独立なら連立してガウスの消去法でlogap1,,logapk\log_{a}p_1,\ldots,\log_{a}p_kについて解ける。 高確率で線形独立になるらしい(証明求む)。p1p-1は合成数だから逆元が存在せずガウスの消去法ができない場合がある。 その場合gcd\gcdを取って互いに素なmodとの計算から中国剰余定理で再構成すればよい。
④ランダムな数ggについて計算してpkp_k-smoothなagb=i=1kpifimodpa^gb = \sum_{i=1}^k p_i^{f_i} \bmod pを探す。この時、指数部比較で g+logba=i=1kfilogapimod(p1)g+\log_b{a}=\sum_{i=1}^k f_i \log_{a}p_i \bmod (p-1) を得る。未知変数はlogba\log_b{a}のみである。よって、ax=bmodpa^x=b \bmod pの解であるlogab\log_a{b}について解くことができる。
*計算量解析
ランダムな数hhについてahmodpa^h \bmod ppkp_k-smoothになる確率を見積ろう。φ(pk):=φ(p_k):=pkp_k-smoothな数の個数」とする。 素数定理からkpk/logpkk \approx p_k/\log{p_k}である。u:=[logpkp]u:=[\log_{p_k} p]とする。 piei\prod p_i^{e_i} について eiu\sum e_i \leq u ならば pkp_k-smoothである。このような数は(u+kk)\binom{u+k}{k}個なので \begin{align} φ(p_k)&\geq \binom{u+k}{k}\\ &\geq (k/u)^u \\ &\approx (p_k/(u \log{p_k}))^u\\ &\approx p (u \log{p_k}))^{-u}\\ &\end{align} なのでおよそ、φ(pk)/puu+o(1)φ(p_k)/p \approx u^{-u+o(1)}である。 従って4k4k個のpkp_k-smoothな数を見つけるのに 平均O(k2uu)O(k^2 u^u)かかる。ガウスの消去法にはO(k3)O(k^3)かかる。 k2uu+k3k^2 u^u + k^3 が最小になるk2logploglogpk\approx \sqrt{\frac{2\log{p}}{\log{\log{p}}}}を取ってくると良いらしいですが示し方が分かりませんでした(加筆求む)。
*問題演習
LOJ:6542: (p<3×1018p < 3 \times 10^{18})

*参考文献
https://www.csa.iisc.ac.in/~chandan/courses/CNT/notes/lec21.pdf