Trait nekolib::math::ModTetration

pub trait ModTetration {
    // Required method
    fn mod_tetration(self, b: Self, n: Self) -> Self;
}

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)$ である¹。

よって、$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) などとも表記される。

---

1. ゆるゆるな bound である。実際にはもっと速く減りそう。 ↩

Required Methods

fn mod_tetration(self, b: Self, n: Self) -> Self

Implementations on Foreign Types

impl ModTetration for u8

fn mod_tetration(self, b: Self, n: Self) -> Self

impl ModTetration for u128

fn mod_tetration(self, b: Self, n: Self) -> Self

impl ModTetration for u64

fn mod_tetration(self, b: Self, n: Self) -> Self

impl ModTetration for u32

fn mod_tetration(self, b: Self, n: Self) -> Self

impl ModTetration for u16

fn mod_tetration(self, b: Self, n: Self) -> Self

impl ModTetration for usize

fn mod_tetration(self, b: Self, n: Self) -> Self

Implementors