Tetration

個人的メモ

$a$ と $p$ が互いに素な場合はオイラーの定理($a^{\phi(p)}) = 1\ \mathrm{mod}\ p$) を用いて ($a ↑↑ b$) の指数部分は $(a ↑↑ (b-1))\ \mathrm{mod}\ \phi(p)$ と等しいことが分かり, これを再帰的に繰り返すことで元の値が求まる(ここで $\phi$ は totient function とする).
$\phi(\phi(\phi(\cdots p \cdots)))$ は $\O (\log (p))$ 回で $1$ に収束する. なぜなら定義から $p$ が偶数なら $\phi(p)$ は $1 / 2$ 以下となり, また $p$ が奇数でも $\phi(p)$ は偶数となるため連続する $2$ 回の間に少なくとも $1 / 2$ になるからである. そのため $b$ が大きかったとしても指数部は $\O (\log (p))$ で $1$ となり, テトレーションを高速に計算することが可能になる.
問題は $a$ と $p$ が互いに素でない場合であるが $p$ を $p = qr$ ($r$ を $a$ と互いに素な $p$ の最大の約数とする) と分解したとき少なくとも $n \ge \lfloor \log_2 p \rfloor$ の整数 $n$ について $a^n \mathrm{mod}\ q$ は $0$ となる. なぜなら定義から $q$ の素因数はすべて $p$ の素因数となっているからである.
また $a^i \mathrm{mod}\ r$ の数列はオイラーの定理($a^{\phi(r)} = 1\ \mathrm{mod}\ r$) より周期 $\phi(r)$ となる. つまり $n \ge \lfloor \log_2 p \rfloor$ の整数 $n$ について $a^n \mathrm{mod}\ q$ が周期 $1$, $a^n \mathrm{mod}\ r$ が周期 $\phi(r)$ を持ち, また $q$ と $r$ は互いに素であることから中国剰余定理より $i \ge \lfloor \log_2 p \rfloor$ について $a^i \mathrm{mod}\ p$ の数列は周期 $\phi(r)$ を持つ.
ここで明示的に $p = qr$ の分解を求めなくても $q$ と $r$ は互いに素であるため $\phi(p) = \phi(q) \phi(r)$ となり上記の結果と合わせて $i \ge \lfloor \log_2 p \rfloor$ について $a^i \mathrm{mod}\ p$ の数列は周期 $\phi(p)$ を持つので $a$ と $p$ が互いに素である場合と同じように $a^n \mathrm{mod}\ p$ は $n\ \mathrm{mod}\ \phi(p)$ を再帰的に計算することで求まる($i < \lfloor \log_2 p \rfloor$ の場合についてはその値を剰余を取らず管理しておく).
実装は剰余が int 型の場合 $\lfloor \log_2 p \rfloor$ は高々 $32$ なので指数部が $32$ 以上となるかどうかに注意して計算をしてもいいが, 任意の自然数 $n$ について $\phi(n) \ge \lfloor \log_2 n \rfloor$ であることから $\phi(p)$ 以上となるかどうかで場合分けをするとよい. つまり実装の 1 つ下の再帰パートでは $a ↑↑ (b-1) \ge \phi(p)$ なら $\phi(p) + ((a ↑↑ (b-1))\ \mathrm{mod}\ \phi(p))$ を $a ↑↑ (b-1) < \phi(p)$ なら $a ↑↑ (b-1)$ を返すことにして処理を進めている.
(注) 剰余 $p$ を $[0, 2 p)$ にマップしているので剰余の値は $2^{31}$ 未満とする.
計算量を考えてみると totient function $\phi$ を求める部分が支配的であり 1 回あたり $\sqrt{p}$ の計算量がかかるが, 先述のように剰余は $2$ 回 $\phi$ をかますと $1 / 2$ 以下となるため $\phi$ の計算にかかる計算量は幾何級数的に小さくなる. よって結局計算量は $O(\sqrt{p})$ となる. 同じ $mod$ について何度も $a↑↑b \ \% mod$ を計算する場合は totient function の値を持っておくと毎回計算しなくて済むので高速化が可能になる.