modに対するアプローチ
Latest Author
37zigen
/Date 2020-01-09 13:33:37 / Views
4884
分解してみる
例題: nCk(mod20) を求めよ。 ただし 0≤k≤n≤106
nCk≡k!n(n−1)(n−2)…(n−k+1)(mod20) なので
{k!}−1(mod20) が計算できればよさそうですが
k! と
20 が互いに素になるかはわかりません。仮に互いに素でない場合は逆元が存在しないのでこのままでは解けません。
そこで
20=22×5 であることに着目して
- n(n−1)(n−2)…(n−k+1)=2t1×5f1×r1
- k!=2t2×5f2×r2
と分解してみます。すると答えは
2t1−t2×5f1−f2×r1×r2−1(mod20) になります。
いま
r2 に
2 と
5 は含まれていないので
r2 と
20 が必ず互いに素になり逆元が計算できます。
「
m1,m2…mk がどの2つも互いに素ならば
- x≡a1(modm1)
- x≡a2(modm2)
- …
- x≡ak(modmk)
をすべて満たす
x が
m1m2…mk を法として一意に存在する」というのが中国人剰余定理です。
f(n)(modm) を直接計算するのは難しい・大変である場合でも、
m=p1e1p2e2...pkek と分解して
- f(n)≡r1(modp1e1)
- f(n)≡r2(modp2e2)
- …
- f(n)≡rk(modpkek)
を計算できたのであればそれらから
f(n)(modm) を計算することができます。
上の問題でいうと
nCk(mod22) と
nCk(mod5) が計算できれば
nCk(mod20) を計算できることになります。
詳細は割愛しますが
nCk(modpe) は前処理に
O(pe) かけることで一回あたり
O(logn) で計算することができます。
逆元を消してみる
- f(n,p):=n! のなかに素数 p が何個含まれているか
上記を定義しておくと
nCk≡2f(n,2)−f(k,2)−f(n−k,2)×3f(n,3)−f(k,3)−f(n−k,3)…(mod20) となります。
こうすると逆元というやっかいな操作を気にする必要がなくなります。
逆元を使った小ネタ
いま
232 と互いに素な
b<232 を考えてみます。 互いに素なので当然
b−1(mod232) が計算できます。
ここで
232 未満の
b の倍数を考えてみると
0, b, 2b…⌊b232−1⌋b があります。これらに
b−1(mod232) を掛け
232 で余りを取ると
0,1,2…⌊b232−1⌋ になります。
また
n≡m(mod232)⇒nb−1≡mb−1(mod232) であるので
232未満で
b の倍数でないものに
b−1(mod232) を掛け
232 で余りを取ると
⌊b232−1⌋ より大きくなります。
つまりこれを使うと掛け算のみで倍数判定を行うことができます。(C++のunsignedではオーバーフローすると0に巻き戻されるので余りを取るのと同じことになります。)
// 2^32未満で3の倍数かどうか判定する
bool is_3k(unsigned n){
return n * 2863311531u <= 1431655765u;
}
離散対数問題
Pohlig–Hellman algorithmを用いて離散対数問題
ax=bmodpeは
O(ep)で解ける。
まず
ax≡bmodpをbaby-step giant-step(BSGS)で求める。
次に
α:=a mod pa,β:=b mod pbとして、
αx≡βmodpeを満たす
xを求める。
α≡β≡1modpだから
g:=(1+p)として
α,βは
gを生成元とする位数
pe−1の巡回群の元。
従って、
α,βの
gによる表示を求められると、
αx≡βmodpeも解ける。
ここでは
α,βを
hと置いて、
gx≡hmodpeを解こう。
hxk,βを
gのべき乗で表したときのべき指数が
p進数で
1桁目から
k桁目まで一致するとする。
すると、
hg−xkはべき指数が
k桁目まで打ち消されるので位数
pe−1−k以下になる。
つまり
(hg−xk)pe−2−kは位数
1または
pとなり、
γ:=gpe−2として
⟨γ⟩の元となる(なぜなら、
γp=1より
⟨γ⟩の位数は
pであるから)。
よって、
(hg−xk)pe−2−kの
γのべき乗による表示
γdk=(hg−xk)pe−2−kがBSGSによって得られる。
γ:=gpe−2を戻して
pdkpk=hg−xkだから
xk+1:=xk+pkdkとなる。
通常のBSGSでは
x=up+vとして
0≤u≤[p]を探索するが、このアルゴリズムでは
γが
kによらないことから
x=uep+vとするとよい。テーブルの構築に
(ep)かかるが、一回のBSGSの実行で見る
uの範囲が
O(ep)となるため全体の計算量も
O(ep)になる。
離散対数問題(2): index calculus algorithm
離散対数問題
ax=bmodpは平均
O(e(3/2+o(1))logploglogp)で解ける。
①小さい方から素数を
k個列挙して
p1,…,pkと置く。
ランダムな数
hについて計算して、
p1,…,pkのみを素因数に持つ
(ahmodp)を探す(
pk-smoothという)。
②そのような
an=∑i=1kpieimodpの指数部比較で
h=i=1∑keilogapimod(p−1)
を得る。
ord(a)∣(p−1)であるから
modp−1を取っている。
ここで、
logap1,…,logapkは未知数である。
③同じような方程式を
4k個用意する。
③そのうち
k個が線形独立なら連立してガウスの消去法で
logap1,…,logapkについて解ける。
高確率で線形独立になるらしい(証明求む)。
p−1は合成数だから逆元が存在せずガウスの消去法ができない場合がある。
その場合
gcdを取って互いに素なmodとの計算から中国剰余定理で再構成すればよい。
④ランダムな数
gについて計算して
pk-smoothな
agb=∑i=1kpifimodpを探す。この時、指数部比較で
g+logba=i=1∑kfilogapimod(p−1)
を得る。未知変数は
logbaのみである。よって、
ax=bmodpの解である
logabについて解くことができる。
*計算量解析
ランダムな数
hについて
ahmodpが
pk-smoothになる確率を見積ろう。
φ(pk):=「
pk-smoothな数の個数」とする。
素数定理から
k≈pk/logpkである。
u:=[logpkp]とする。
∏piei について
∑ei≤uならば
pk-smoothである。このような数は
(ku+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)/p≈u−u+o(1)である。
従って
4k個の
pk-smoothな数を見つけるのに
平均
O(k2uu)かかる。ガウスの消去法には
O(k3)かかる。
k2uu+k3が最小になる
k≈loglogp2logpを取ってくると良いらしいですが示し方が分かりませんでした(加筆求む)。
*問題演習
LOJ:6542: (
p<3×1018)
*参考文献
https://www.csa.iisc.ac.in/~chandan/courses/CNT/notes/lec21.pdf