3 (Favした一覧ページはユーザーページから) Tweet

分解してみる

例題: ${}_n \mathrm{C} _k \pmod{20}$ を求めよ。 ただし $0\leq k \leq n \leq 10^{6}$

${}_n \mathrm{C} _k \equiv \frac{n (n-1) (n-2) \ldots (n-k+1)}{k!} \pmod{20}$ なので $\{k!\}^{-1} \pmod{20}$ が計算できればよさそうですが
$k!$ と $20$ が互いに素になるかはわかりません。仮に互いに素でない場合は逆元が存在しないのでこのままでは解けません。
そこで $20 = 2^{2} \times 5$ であることに着目して

• $n (n-1) (n-2) \ldots (n-k+1) = 2^{t_1}\times 5^{f_1}\times r_{1}$
• $k! = 2^{t_2}\times 5^{f_2}\times r_{2}$

と分解してみます。すると答えは $2^{t_1 - t_2}\times 5^{f_1 - f_2}\times r_1 \times {r_2}^{-1} \pmod{20}$ になります。
いま $r_{2}$ に $2$ と $5$ は含まれていないので $r_{2}$ と $20$ が必ず互いに素になり逆元が計算できます。

中国人剰余定理

「$m_{1}, m_{2} \ldots m_{k}$ がどの2つも互いに素ならば

• $x \equiv a_{1} \pmod{m_{1}}$
• $x \equiv a_{2} \pmod{m_{2}}$
• $\ldots$
• $x \equiv a_{k} \pmod{m_{k}}$

をすべて満たす $x$ が $m_{1} m_{2} \ldots m_{k}$ を法として一意に存在する」というのが中国人剰余定理です。

$f(n) \pmod m$ を直接計算するのは難しい・大変である場合でも、$m = {p_1}^{e_1} {p_2}^{e_2} ... {p_k}^{e_k}$ と分解して

• $ f(n) \equiv r_1 \pmod{{p_1}^{e_1}}$
• $ f(n) \equiv r_2 \pmod{{p_2}^{e_2}}$
• $ \ldots$
• $ f(n) \equiv r_k \pmod{{p_k}^{e_k}}$

を計算できたのであればそれらから $f(n) \pmod m$ を計算することができます。

上の問題でいうと ${}_n \mathrm{C} _k \pmod{2^{2}}$ と ${}_n \mathrm{C} _k \pmod{5}$ が計算できれば ${}_n \mathrm{C} _k \pmod{20}$ を計算できることになります。
詳細は割愛しますが ${}_n \mathrm{C} _k \pmod{p^e}$ は前処理に $O(p^e)$ かけることで一回あたり $O(\log n)$ で計算することができます。

逆元を消してみる

• $f(n, p) := n!$ のなかに素数 $p$ が何個含まれているか

上記を定義しておくと ${}_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}$ となります。
こうすると逆元というやっかいな操作を気にする必要がなくなります。

逆元を使った小ネタ

いま $2^{32}$ と互いに素な $b < 2^{32}$ を考えてみます。 互いに素なので当然 $b^{-1} \pmod{2^{32}}$ が計算できます。
ここで $2^{32}$ 未満の $b$ の倍数を考えてみると $0,\ b,\ 2b \ldots \lfloor \frac{2^{32}-1}{b} \rfloor b$ があります。これらに $b^{-1} \pmod{2^{32}}$ を掛け $2^{32}$ で余りを取ると $0, 1, 2 \ldots \lfloor \frac{2^{32}-1}{b} \rfloor$ になります。
また $n \not\equiv m \pmod{2^{32}} \Rightarrow nb^{-1} \not\equiv mb^{-1} \pmod{2^{32}}$ であるので $2^{32}$未満で $b$ の倍数でないものに $b^{-1} \pmod{2^{32}}$ を掛け $2^{32}$ で余りを取ると $\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を用いて離散対数問題$a^x = b \bmod p^e$は$O(\sqrt{ep})$で解ける。 まず$a^x\equiv b\bmod p$をbaby-step giant-step(BSGS)で求める。 次に$\alpha:=\frac{a}{a\ \bmod\ p},\beta:=\frac{b}{b\ \bmod\ p}$として、$\alpha^x\equiv \beta\bmod p^e$を満たす$x$を求める。 $\alpha\equiv\beta\equiv1\bmod p$だから$g:=(1+p)$として$\alpha,\beta$は$g$を生成元とする位数$p^{e-1}$の巡回群の元。 従って、$\alpha,\beta$の$g$による表示を求められると、$\alpha^x\equiv \beta \bmod p^e$も解ける。 ここでは$\alpha,\beta$を$h$と置いて、$g^x\equiv h\bmod p^e$を解こう。 $h^{x_k},\beta$を$g$のべき乗で表したときのべき指数が$p$進数で$1$桁目から$k$桁目まで一致するとする。 すると、$hg^{-x_k}$はべき指数が$k$桁目まで打ち消されるので位数$p^{e-1-k}$以下になる。 つまり$(hg^{-x_k})^{p^{e-2-k}}$は位数$1$または$p$となり、$\gamma:=g^{p^{e-2}}$として$\langle \gamma \rangle$の元となる（なぜなら、$\gamma^p=1$より$\langle\gamma\rangle$の位数は$p$であるから）。 よって、$(hg^{-x_k})^{p^{e-2-k}}$の$\gamma$のべき乗による表示$\gamma^{d_k}=(hg^{-x_k})^{p^{e-2-k}}$がBSGSによって得られる。 $\gamma:=g^{p^{e-2}}$を戻して$p^{d_kp^k}=hg^{-x_k}$だから$x_{k+1}:=x_k+p^kd_k$となる。 通常のBSGSでは$x=u\sqrt{p}+v$として$0\leq u\leq [\sqrt p]$を探索するが、このアルゴリズムでは$\gamma$が$k$によらないことから$x=u\sqrt{ep}+v$とするとよい。テーブルの構築に$(\sqrt{ep})$かかるが、一回のBSGSの実行で見る$u$の範囲が$O(\sqrt{\frac{p}{e}})$となるため全体の計算量も$O(\sqrt{ep})$になる。

離散対数問題(2): index calculus algorithm

離散対数問題$a^x=b \bmod p$は平均$O(e^{(3/\sqrt{2}+o(1))\sqrt{\log{p}\log\log{p}}})$で解ける。
①小さい方から素数を$k$個列挙して$p_1,\ldots,p_k$と置く。 ランダムな数$h$について計算して、$p_1,\ldots,p_k$のみを素因数に持つ$(a^h \bmod p)$を探す($p_k$-smoothという)。
②そのような$a^n=\sum_{i=1}^k p_i^{e_i} \bmod p$の指数部比較で $$h=\sum_{i=1}^k e_i \log_{a} p_i \bmod (p-1)$$ を得る。$\mathrm{ord}(a)|(p-1)$であるから$\mod p-1$を取っている。 ここで、$\log_{a}p_1,\ldots,\log_{a}p_k$は未知数である。
③同じような方程式を$4k$個用意する。
③そのうち$k$個が線形独立なら連立してガウスの消去法で$\log_{a}p_1,\ldots,\log_{a}p_k$について解ける。 高確率で線形独立になるらしい(証明求む)。$p-1$は合成数だから逆元が存在せずガウスの消去法ができない場合がある。 その場合$\gcd$を取って互いに素なmodとの計算から中国剰余定理で再構成すればよい。
④ランダムな数$g$について計算して$p_k$-smoothな$a^gb = \sum_{i=1}^k p_i^{f_i} \bmod p$を探す。この時、指数部比較で $$g+\log_b{a}=\sum_{i=1}^k f_i \log_{a}p_i \bmod (p-1)$$ を得る。未知変数は$\log_b{a}$のみである。よって、$a^x=b \bmod p$の解である$\log_a{b}$について解くことができる。
＊計算量解析
ランダムな数$h$について$a^h \bmod p$が$p_k$-smoothになる確率を見積ろう。$φ(p_k):=$「$p_k$-smoothな数の個数」とする。 素数定理から$k \approx p_k/\log{p_k}$である。$u:=[\log_{p_k} p]$とする。 $\prod p_i^{e_i}$ について $\sum e_i \leq u $ならば $p_k$-smoothである。このような数は$\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} なのでおよそ、$φ(p_k)/p \approx u^{-u+o(1)}$である。 従って$4k$個の$p_k$-smoothな数を見つけるのに 平均$O(k^2 u^u)$かかる。ガウスの消去法には$O(k^3)$かかる。 $k^2 u^u + k^3 $が最小になる$k\approx \sqrt{\frac{2\log{p}}{\log{\log{p}}}}$を取ってくると良いらしいですが示し方が分かりませんでした（加筆求む）。
＊問題演習
LOJ:6542: ($p < 3 \times 10^{18}$)

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