Trait nekolib::math::ModTetration
source · pub trait ModTetration {
// Required method
fn mod_tetration(self, b: Self, n: Self) -> Self;
}Expand description
tetration。
${}^b a\bmod n$ を求める。${}^\bullet \bullet$ は次のように定義される。 $$ {}^b a = \begin{cases} 1, & \text{if } b = 0; \\ a^{\left({}^{(b-1)} a\right)}, & \text{if } b \ge 1. \end{cases} $$ 直感的に書けば、$\underbrace{a^{(a^{(\cdots ^a)})}}_{b\text{ many}} \bmod n$ である。
Idea
大変大きくなりうる $z$ に対して $a^z\bmod n$ を求めることを考える。
このとき、dlog の Idea と同じ議論から、ある $\mu$, $\lambda$ が存在して
$z\lt\mu$ または $z=\mu+q\cdot\lambda+r$ とでき、後者のとき
$a^z\equiv a^{\mu+r}\pmod{n}$ が成り立つ。
ここで、$\mu\le\log_2(n)$, $\lambda\sqsubseteq\varphi(n)$ である。 さらに、任意の $n$ に対して $\log_2(n)\le\varphi(n)$ なので、$z\ge\varphi(n)$ ならば $z\ge\mu$ とわかる。よって、以下のようにできる。 $$ \begin{aligned} a^z \equiv \begin{cases} a^z, & \text{if }z\lt \varphi(n); \\ a^{(z\bmod\varphi(n))+\varphi(n)}, & \text{otherwise}. \end{cases} \end{aligned} $$
直感的には、指数部が $\varphi(n)$ 以上であればすでに周期の中に入っており、入った後は $\varphi(n)$ を法として合同かつ $\varphi(n)$ 以上の値さえ得られれば十分ということである。
When $b$ is large
前述のように、${}^b a\bmod{n}$ を求める際に ${}^{b-1} a$ を法 ${\varphi(n)}$ で考える。 その次は $\varphi(\varphi(n)), \varphi(\varphi(\varphi(n))), \dots$ と続く。 $\varphi^\star(n)$ 段では考えるべき法が $1$ となり、それより上の段のことは無視できる。
そこで、$\varphi^\star(n)$ を考える。奇素数 $p$ に対して $\varphi(p^e)=p^{e-1}\cdot(p-1)$ が偶数であることと、$\varphi(2^e)=2^{e-1}$ であることから、$\varphi(\varphi(n))\lt n/2$ が成り立つ。すなわち、$\varphi^\star(n)\le 2\log(n)$ である1。
よって、$b\ge 2\log(n)$ であれば ${}^{b+1} a\equiv {}^b a\pmod{n}$ となる。
Common bugs
繰り返し二乗法で $\varphi(n)$ 以上か判断しつつ $a^z\bmod\varphi(n)$ を求める際、 $a^{2^\bullet}$ が $\varphi(n)$ 以上になった時点で $a^z\ge\varphi(n)$ と判断してしまうと、誤検出してしまう場合がある。
fn mod_pow(mut a: u64, mut b: u64, n: u64) -> u64 {
let mut res = 1 % n;
let mut large = false;
while b > 0 {
if b & 1 == 1 {
res *= a;
if res >= n { res %= n; large = true; }
}
a *= a;
if a >= n { a %= n; large = true; } // !
b >>= 1;
}
if large { res + n } else { res }
}最後のループで初めて a >= n になると、res < n なのに res + n が返ってしまう。
このバグや、あるいはそもそも $z\ge\varphi(n)$ を仮定していることなどにより、
${}^3 2\bmod 32 = 0$ としてしまうコードがたくさん提出されている。
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
$\bullet$
Complexity
$O(\sqrt{n})$ time.
律速は、$\varphi(n), \varphi(\varphi(n)), \dots$ を求めるパートであり、 $O(\sum_{i=0}^{\varphi^\star(n)} \sqrt{n/2^i}) = O(\sqrt{n})$ である。
Examples
use nekolib::math::ModTetration;
let n = 10_u64.pow(9);
assert_eq!(0_u64.mod_tetration(0, n), 1);
assert_eq!(0_u64.mod_tetration(1, n), 0);
assert_eq!(0_u64.mod_tetration(2, n), 1);
assert_eq!(0_u64.mod_tetration(3, n), 0);
assert_eq!(1_u64.mod_tetration(0, n), 1);
assert_eq!(1_u64.mod_tetration(1, n), 1);
assert_eq!(2_u64.mod_tetration(0, n), 1);
assert_eq!(2_u64.mod_tetration(1, n), 2);
assert_eq!(2_u64.mod_tetration(2, n), 4);
assert_eq!(2_u64.mod_tetration(3, n), 16);
assert_eq!(2_u64.mod_tetration(4, n), 65536);
assert_eq!(3_u64.mod_tetration(9, n), 64_195_387);
assert_eq!(3_u64.mod_tetration(10, n), 464_195_387);
assert_eq!(3_u64.mod_tetration(11, n), 464_195_387);
assert_eq!(3_u64.mod_tetration(99, n), 464_195_387);Notations
${}^b a$ は $a\uparrow\uparrow b$ (Knuth’s up-arrow notation) や $a\to b\to 2$ (Conway chained arrow notation) などとも表記される。
ゆるゆるな bound である。実際にはもっと速く減りそう。 ↩