G - Discrete Logarithm Problems Editorial by kyopro_friends
予め \(O(\sqrt{P})\) 時間掛けて \(P-1\) を素因数分解し、\(P-1=\prod_{k=1}^{n} p_k ^{e_k}\) とします。
\(1\leq x < P\) に対し、\(x^m=1 \bmod P\) を満たす最小の正整数 \(m\) を ( \((\mathbb{Z}/P\mathbb{Z})^*\) における) 位数といいます。任意の \(x\) についてその位数は \(P-1\) の約数になります。
証明
$x$ の位数を $m$ とし、$d=\gcd(m,P-1)$ とします。拡張ユークリッドの互除法からある整数 $a,b$ が存在して $am+b(P-1)=d$ となります。 フェルマーの小定理より $x^{P-1}\equiv 1$ なので、$x^d = x^{am+b(P-1)} = (x^m)^a(x^{P-1})^{-b}\equiv 1$ となり、位数の最小性から $d\geq m$ となります。一方、gcd の性質から$d|m$ なので $d=m$ であり、$d|P-1$ より $m|P-1$ となります。このことから、任意の \(x\) に対し、その位数は次の手順により求めることができます。
- \(M\) を \(P-1\) とする
- \(k=1,2,\ldots,n\) の順に以下を繰り返す
- \(p_k|M\) かつ \(x^{\frac{M}{p_k}}=1 \bmod p\) である限り、\(M\) を \(\frac{M}{p_k}\) に置き換える操作を繰り返す
- 全ての操作が終了した時点の \(M\) が \(x\) の位数である
繰り返しは全体で \(\sum_i e_i=O(\log P)\) 回であり、各繰り返しにおいて判定に \(O(\log P)\) の時間がかかるので、この手順は \(O((\log P)^2)\) 時間で行なえます。
\(B_i\) を \(A_i\) の位数とします。このとき、次の \(2\) 条件は同値になります：
- ある正整数 \(k\) が存在して、\(A_i^k=A_j \bmod P\)
- \(B_j | B_i\)
証明
$\bmod P$ における原始根 $g$ を任意に1つとり固定する。補題1：$g^e$ の位数は $\frac{(P-1)}{\gcd(P-1,e)}$ である。
証明：$g^e$ の位数を $o$、$\gcd(P-1,e)$ を $d$ とする。位数の定義から $o$ は $(g^e)^o\equiv 1 \bmod P$ を満たす最小の非負整数であり、原始根の定義からこの条件は$eo\equiv 0 \bmod P-1$ と同値なので $eo=\mathrm{lcm}(e,P-1)$ となる。$(P-1)e=\gcd(e,P-1)\mathrm{lcm}(e,P-1)$ であることから、$do=P-1$ となり示せた。
補題2：「ある非負整数 $k$ が存在して、$(g^{e_1})^k\equiv g^{e_2} \bmod P$ となる」(1)ことと「$\gcd(e_1,P-1)|\gcd(e_2,P-1)$ を満たす」(2)ことは同値である。
証明：前者の条件は $e_1k\equiv e_2 \bmod P-1$ となる $k$ が存在することと同値なのでこの条件で考える。
(1)⇒(2)
対偶を示す。$\gcd(e_1,P-1) \not |\gcd(e_2,P-1)$ のとき、$\gcd(P-1,e)$ の約数 $d$ であって、$\gcd(e_2,P-1)$ の約数でないものが存在する。この $d$ に対し、任意の $k$ で $e_2 \not\equiv 0\equiv e_1k \mod d$ が成り立ち、これは mod を $d$ の倍数である $P-1$ に置き換えても成り立つ。
(2)⇒(1)
$d_i=\gcd(e_i,P-1),\ e_i'=\frac{e_i}{d_i}$ とする。$e_1k \equiv e_2 \bmod P-1$ となる $k$ の存在を示せば良い。両辺を $d_1$ で割り、$e_1'k\equiv e_2'\frac{d_2}{d_1} \bmod\frac{P-1}{d_1}$ をえる。$e_1'$ は定義から $P-1$ と互いに素なので $e_1'^{-1}\bmod\frac{P-1}{d_1}$ が存在し $k\equiv e_1'^{-1}e_2'\frac{d_2}{d_1} \bmod\frac{P-1}{d_1}$ を満たす任意の非負整数 $k$ が条件を満たす。
補題3：$x|z,\ y|z$ に対し、$x|y$ であることと、$\displaystyle \frac{z}{y} |\frac{z}{x}$ であることは同値
証明：略
元の主張の証明：
$B_i'$ を $A_i\equiv g^{B_i'} \bmod P$ を満たす最小の非負整数とする。「ある非負整数 $k$ が存在して、$A_i^k\equiv A_j \bmod P$ となる」ことは補題2より「$\gcd(B_i',P-1)|\gcd(B_j',P-1)$ を満たす」ことと同値である。これは補題3より「$\frac{P-1}{\gcd(B_j',P-1)}|\frac{P-1}{\gcd(B_i',P-1)}$ を満たす」ことと同値であり、補題1より $B_j|B_i$ と同値である。
よって、各 \(B_i\) を実際に求めることで、問題は次のように読み替えられました。
問題(★)：\(P-1\) の約数である \(N\) 個の整数 \(B_1,\ldots,B_N\) が与えられる。\(1\leq i,j \leq N\) を満たす整数の組 \( (i,j)\) であって、\(B_j | B_i\) を満たすものの個数を求めよ
\(B_i\) の値はいずれも \(P-1\) の約数であることから、(\(i\) ではなく) \(B_i\) ごとに整除条件を愚直に確認することで、問題(★)は \(\Theta((P-1\text{ の約数の個数})^2)\) 時間で解くことができます。制約の条件下では \(P-1=6746328388800, 9092877393600\) のとき、\(P-1\) の約数は最大の \(10080\) 個となるため、多くの言語では AC を得ることができます。
問題(★)に対するより高速な解法もあります。\(B_i=\prod_{k=1}^{n}p_k^{e_{i,k}}\) とすると、\(B_j | B_i\) であることは、全ての \(k\) で \(e_{j,k}\leq e_{i,k}\) を満たすことと同値です。よって、高速ゼータ変換(多次元累積和)を考えることで、\(i\) ごとに \(B_j | B_i\) となる \(j\) の個数を求めることができます（分かりにくければ \(P=13,37,109\) などの簡単なケースを考えてみましょう）。計算量は \(O(n*(P-1\text{ の約数の個数}))\) であり、\(n=O(\log P / \log\log P)\) です。
位数を求める手順において、\(M\) を素因数分解された形と同時に管理することで、\(e_{i,k}\) は追加の計算なしで求めることができます。
posted:
last update: