\(P-1\) の素因数分解 \(\displaystyle P-1 = \prod _ {i=0} ^ {n-1} p_i ^ {e_i}\) の前計算の下で、位数の計算をクエリ毎 \(O((\log P)(\log \log P))\) 時間で計算する方法を説明します。

\(1\) 以上 \(P\) 未満の整数 \(x\) の位数 \(m\) を計算したいとします。公式解説 で説明されているように \(m\) は \(P-1\) の約数であり、つまり \(m=\prod _ {i=0} ^ {n-1} p _ i ^ {f _ i}\ (0\leq f _ i\leq e _ i)\) と表せます。\(f _ i\) が求まれば \(\sum _ {i = 0} ^ {n - 1} e _ i = O(\log P)\) より \(m\) の復元は \(O(\log P)\) 時間で可能です。

以降は \(f _ i\) の計算方法を考えます。

\(0\leq l\leq r\leq n\) なる整数 \(l,r\) に対して\(\displaystyle E(l,r)\coloneqq \prod _ {i = l} ^ {r - 1} p _ i ^ {e _ i}\) と定めます。また \(\displaystyle \overline{E}(l,r)\coloneqq E(0,l)\cdot E(r,n)\) および \(\overline{X}(l,r)\coloneqq x ^ {\overline{E}(l,r)} \bmod P\) と定めます。

\(\overline{X}(i,i+1)\) を用いれば次の手順で \(f_i\) を計算できます。

1. \(\mathtt{def}\) \(f(i)\colon\)
2. \(\quad\) \(v\gets \overline{X}(i,i+1)\)
3. \(\quad\) \(\mathtt{for}\) \(j=0,1,\ldots,e_i-1\colon\)
4. \(\quad\quad\) \(\mathtt{if}\) \(v=1\colon\)
5. \(\quad\quad\quad\) \(\mathtt{return}\) \(j\)
6. \(\quad\quad\) \(\mathtt{else}\colon\)
7. \(\quad\quad\quad\) \(v\gets v ^ {p_i} \bmod P\)
8. \(\quad\mathtt{return}\) \(e_i\)

\(\overline{X}(i,i+1)\) が既知であれば (i.e., 2 行目の計算量を無視すれば)、この手続きの計算量は \(O(e_i \log p_i)\) です。つまり、全ての \(i\) に対してこれを行うと \(O(\sum _ {i = 0} ^ {n - 1} e _ i \log p _ i) = O(\log (\prod _ {i = 0} ^ {n - 1} p _ i ^ {e _ i})) = O(\log P)\) 時間です。

あとは \(\overline{X}(i,i+1)\) を計算する方法を考えればよいですが、これはhttps://x.com/noshi91/status/1317022141599002624?s=20 の手法をそのまま適用すれば \(O((\log P)(\log n))\) 時間で可能です。

一応リンク先の手法について改めて説明します。

\(l\leq m\leq r\) なる \(m\) に対して \(\displaystyle \overline{E}(l,m) = \overline{E}(l,r) \cdot E(m, r)\) および \(\overline{X}(l,m) = \overline{X}(l, r) ^ {E(m,r)} \bmod P\) が成り立ちます。

同様に \(\displaystyle \overline{E}(m,r) = \overline{E}(l,r) \cdot E(l, m)\) および \(\overline{X}(m,r) = \overline{X}(l, r) ^ {E(l,m)} \bmod P\) が成り立ちます。

つまり、\(\overline{X}(0,n)=x\) から始めて次のような分割統治法を行うことで \(\overline{X}_i \coloneqq \overline{X}(i,i+1)\) を列挙できます。なお、実装によっては \(n=0\) つまり \(P=2\) の場合を特別に処理する必要があるので注意してください。

1. \(\mathtt{def}\) \(\mathrm{dfs}(l, r, \overline{X}(l, r))\)
2. \(\quad\) \(\mathtt{if}\) \(r - l = 1\colon\)
3. \(\quad\quad\) \(\overline{X}_l \gets \overline{X}(l, r)\)
4. \(\quad\quad\) \(\mathtt{return}\)
5. \(\quad\) \(m\gets \lfloor (l + r) / 2\rfloor\)
6. \(\quad\) \(\mathrm{dfs}(l, m, \overline{X}(l, r) ^ {E(m,r)} \bmod P)\)
7. \(\quad\) \(\mathrm{dfs}(m, r, \overline{X}(l, r) ^ {E(l,m)} \bmod P)\)

計算量を考えます。\(E(\ast,\ast)\) は \(x\) に依存しないので全て前計算しておくことにします。

\(\overline{X}(l, r) ^ {E(m,r)} \bmod P\) の計算は二分累乗法で \(O(\log E(m,r)) = O(\sum _ {i = m} ^ {r - 1}e _ i \log p_i)\) 時間で可能です。同様に \(\overline{X}(l, r) ^ {E(l,m)} \bmod P\) の計算は \(O(\sum _ {i = l} ^ {m - 1}e _ i\log p_i)\) 時間で可能です。

\(m = \lfloor (l + r) / 2\rfloor\) として取っているので再帰の深さは \(O(\log n)\) であり、即ち再帰全体の計算量は \(O((\log n) \sum _ {i = 0} ^ {n - 1} e _ i \log p _ i) = O((\log n)(\log P))\) 時間となります。

以下の論文の Theorem 11 によると \(n = O\left(\dfrac{\log P}{\log \log P}\right)\) なのでこれは \(O((\log P)(\log \log P))\) と評価できます。

• Robin, Guy (1983). “Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n”. Acta Arith. 42: 367–389.

実装例 (C++ 20 (gcc 12.2))