擬似乱数

$s_0,\dots,s_{\lvert\mathcal S\rvert}$ の $\lvert\mathcal S\rvert+1$ 個は $\mathcal S$ の元なので、鳩の巣原理 により $0\le i< j\le\lvert\mathcal S\rvert$ で $s_i=s_j$ となるものがある。$s_{n+1}$ は $s_n$ だけで決まるので、帰納法で $n\ge i$ のすべてで $s_{n+(j-i)}=s_n$ である。よって周期が存在し、周期は $j-i$ 以下なので $\lvert\mathcal S\rvert$ 以下である。$f$ が全単射なら、周期を $\rho$ とし、それを与える $n_0$ をとると、$s_{n_0+\rho}=s_{n_0}$ に $f^{-1}$ を $n_0$ 回施して $s_\rho=s_0$ を得るので、帰納法で $n\ge0$ のすべてで $s_{n+\rho}=s_n$ である。$\square$

$a=1$ なら $W_n(a)=n$ なので正しい。$a\ne1$ とし、$t:=a-1$、$k:=v_p(t)$ とおく（$k\ge1$、$p=2$ なら $k\ge2$）。$W_n(a)=0$ は $a^n=1$ を意味し、$a\ne1$ の整数では $a=-1$ に限る。このとき $a-1=-2$ は、$p$ が奇数なら $p$ で割り切れず、$p=2$ なら $4$ で割り切れないので、仮定に反する。よって $W_n(a)\ne0$ である。
段 1（$p\nmid n$）。$a\equiv1\pmod p$ なので $W_n(a)\equiv n\not\equiv0\pmod p$ であり、$v_p(W_n(a))=0=v_p(n)$ である。
段 2（$n=p$）。$a^i=(1+t)^i\equiv1+it\pmod{t^2}$ なので $W_p(a)\equiv p+t\cdot\frac{p(p-1)}2\pmod{t^2}$ である。$p$ が奇数なら $\frac{p-1}2$ は整数で、$t\cdot\frac{p(p-1)}2$ と $t^2$ はどちらも $p^2$ で割り切れるので、$W_p(a)\equiv p\pmod{p^2}$、すなわち $v_p(W_p(a))=1$ である。$p=2$ なら $W_2(a)=2+t$ で $4\mid t$ なので $v_2(W_2(a))=1$ である。さらに $a^p-1=tW_p(a)$ なので $v_p(a^p-1)=k+1$ であり、$a^p$ も仮定を満たす。
段 3（一般の $n$）。$\sum_{i< uv}a^i=\sum_{j< v}a^{uj}\sum_{i< u}a^i$ より $W_{uv}(a)=W_u(a)\,W_v(a^u)$ である。$v_p(n)$ についての帰納法で示す。$v_p(n)=0$ は段 1 である。$n=pn'$ なら $W_n(a)=W_p(a)W_{n'}(a^p)$ であり、段 2 と、$a^p$ に帰納法の仮定を当てたものから $v_p(W_n(a))=1+v_p(n')=v_p(n)$ である。$\square$

段 1（1 と 2 の同値）。種 $x_0$ からの周期が $m$ なら、$x_{n_0},\dots,x_{n_0+m-1}$ は相異なる $m$ 個の元で、$\mathbb Z_m$ 全体である。$f$ はこれらを順に次へ送るので、$f$ は $\mathbb Z_m$ 全体を 1 つの輪で回る全単射である。すると、どの種からも周期は $m$ である。逆は明らかである。さらにこのとき $\gcd(a,m)=1$ である。実際、$d:=\gcd(a,m)>1$ なら $f(0)=f(m/d)$ で $f$ は単射でない。
段 2（(i) が必要なこと）。$d:=\gcd(c,m)>1$ とする。$x_{n+1}\equiv ax_n\pmod d$ なので、種 $x_0=0$ からの列はすべて $d$ の倍数であり、$1$ が現れない。よって 2 が成り立たない。
段 3（和の言葉に直す）。以下 $\gcd(a,m)=\gcd(c,m)=1$ とする。$f$ は全単射なので、2 は「$f^n(0)=0$ となる最小の $n\ge1$ が $m$ である」ことと同値である。$f^n(0)\equiv cW_n(a)$ で $c$ は法 $m$ で逆元をもつので、これは「$m\mid W_n(a)$ となる最小の $n\ge1$ が $m$ である」ことと同値である。一般に、法 $M$ について $\gcd(a,M)=1$ のとき、$h(x):=(ax+1)\bmod M$ は $\mathbb Z_M$ の全単射で $h^n(0)=W_n(a)\bmod M$ なので、$M\mid W_n(a)$ となる最小の $n\ge1$ が存在して $M$ 以下である。これを $N(M)$ と書く。$M\mid W_N(a)$（$N=N(M)$）なら $a^N-1=(a-1)W_N(a)\equiv0$ なので、$W_{N+k}(a)=W_N(a)+a^NW_k(a)\equiv W_k(a)\pmod M$ である。よって $W_n(a)\bmod M$ は $n\bmod N$ だけで決まり、$M\mid W_n(a)\iff N(M)\mid n$ である。
段 4（素数の冪に分ける）。$m=p_1^{e_1}\cdots p_r^{e_r}$ と素因数分解すると、$m\mid W_n(a)$ はすべての $i$ で $p_i^{e_i}\mid W_n(a)$、すなわち $N(p_i^{e_i})\mid n$ と同値なので、$N(m)=\operatorname{lcm}_iN(p_i^{e_i})$ である。$N(p_i^{e_i})\le p_i^{e_i}$ なので $N(m)\le\prod_iN(p_i^{e_i})\le m$ であり、$N(m)=m$ はすべての $i$ で $N(p_i^{e_i})=p_i^{e_i}$ となることと同値である（逆向きは、互いに素な数の最小公倍数が積であることによる）。
段 5（素数の冪 $p^e$ の場合）。$p\nmid a$ のもとで、$N(p^e)=p^e$ は「$p\mid a-1$、かつ $p=2$、$e\ge2$ なら $4\mid a-1$」と同値であることを示す。

• 条件が成り立つとき：$p=2$、$e=1$ なら $a$ は奇数で $W_n(a)\equiv n\pmod2$ なので $N(2)=2$ である。それ以外では lem-prng-valuation により $p^e\mid W_n(a)\iff e\le v_p(n)\iff p^e\mid n$ なので $N(p^e)=p^e$ である。
• $a\not\equiv1\pmod p$ のとき：$a-1$ は法 $p^e$ で逆元をもつので、$p^e\mid W_n(a)\iff a^n\equiv1\pmod{p^e}$ である。Eulerの定理(整数論) により $n=\varphi(p^e)=p^{e-1}(p-1)$ はこれを満たすので、$N(p^e)\le p^{e-1}(p-1)< p^e$ である。
• $p=2$、$e\ge2$、$a\equiv3\pmod4$ のとき：$W_{2k}(a)=(1+a)W_k(a^2)$ である。$a^2\equiv1\pmod8$ なので lem-prng-valuation を $a^2$ に当てると、$k=2^{e-2}$ について $v_2(W_{2^{e-1}}(a))=v_2(1+a)+(e-2)\ge e$ である。よって $N(2^e)\le2^{e-1}< 2^e$ である。
  段 6（まとめ）。段 1〜4 から、2 は「$\gcd(a,m)=1$、(i)、すべての $i$ で $N(p_i^{e_i})=p_i^{e_i}$」と同値であり、段 5 から最後の条件は (ii) と (iii) を合わせたものと同値である（$p=2$、$e\ge2$ は $4\mid m$ のことである）。(ii) は $\gcd(a,m)=1$ を含むので、2 と 3 は同値である。$\square$

$f$ は全単射なので、thm-prng-eventual により列ははじめから繰り返し、周期は $x_n=x_0$ となる最小の $n\ge1$ である。$x_n\equiv a^nx_0$ で $x_0$ は法 $p$ で逆元をもつので、$x_n=x_0\iff a^n\equiv1\pmod p$ である。よって周期は $\operatorname{ord}_p(a)$ で、Fermatの小定理 から $p-1$ の約数である。$\operatorname{ord}_p(a)=p-1=\varphi(p)$ は 原始根 の定義「乗法的位数と原始根」そのものである。$\square$

$x_{n+j}\equiv a^jx_n+cW_j(a)\pmod m$（$W_0(a):=0$）なので
$$ \sum_jb_jx_{n+j}\equiv\Bigl(\sum_jb_ja^j\Bigr)x_n+c\sum_jb_jW_j(a)\equiv K\pmod m,\qquad K:=c\sum_jb_jW_j(a) $$
であり、$K$ は $n$ によらない。$m$ で割ると、$\sum_jb_j\frac{x_{n+j}}m\in\frac Km+\mathbb Z$ である。一方、$P:=\sum_{b_j>0}b_j$、$Q:=\sum_{b_j< 0}\lvert b_j\rvert$ とおくと、$0\le x/m< 1$ より $\sum_jb_j\frac{x_{n+j}}m$ は $-Q$ より大きく $P$ より小さいか、$P=0$ なら $0$ 以下、$Q=0$ なら $0$ 以上である。いずれにせよ値は長さ $P+Q$ の半開区間に入り、そこに入る $\frac Km+\mathbb Z$ の元は高々 $P+Q$ 個である。$c=0$ なら $K=0$ で値は整数であり、$P,Q>0$ なら値は開区間 $(-Q,P)$ に入るので、その整数 $-Q+1,\dots,P-1$ の $P+Q-1$ 個のどれかである。値が同じ点は同じ超平面に乗るので、主張が従う。$\square$

$P(r):=\Pr[G(\sigma)=r]$、$U(r):=1/\lvert\mathcal R\rvert$ とおく。$r\in G(\mathcal S)$ なら $P(r)\ge1/\lvert\mathcal S\rvert>U(r)$、$r\notin G(\mathcal S)$ なら $P(r)=0$ である。$T_0$ については $\Pr[T_0(G(\sigma))=1]=1$、$\Pr[T_0(\tau)=1]=\lvert G(\mathcal S)\rvert/\lvert\mathcal R\rvert$ で、等式を得る。不等号は $\lvert G(\mathcal S)\rvert\le\lvert\mathcal S\rvert$ による。
最大であること：乱数を使わない検定 $T$ について $A:=T^{-1}(1)$ とおくと、$\Pr[T(G(\sigma))=1]-\Pr[T(\tau)=1]=\sum_{r\in A}(P(r)-U(r))$ である。$P-U$ が正になるのは $G(\mathcal S)$ の上だけなので、これは $\sum_{r\in G(\mathcal S)}(P(r)-U(r))=\operatorname{Adv}_G(T_0)$ 以下である。$A$ を補集合に替えると符号が変わるだけなので（$\sum_r(P(r)-U(r))=0$）、絶対値も $\operatorname{Adv}_G(T_0)$ 以下である。乱数を使う検定の優位度は、乱数を固定した検定の差の平均の絶対値なので、やはり $\operatorname{Adv}_G(T_0)$ 以下である。$\square$

$r=G(\sigma)$ なら $T(r)=1$ は予測が当たることなので、確率は $\frac12+\varepsilon$ である。$r=\tau$ が一様なら、$\tau_i$ は先頭の $i$ ビットおよび $A$ の乱数と独立で一様なので、予測がどんな値でも当たる確率は $\frac12$ である。差は $\varepsilon$ である。$\square$