Title 疑似乱数生成器の安全性とモンテカルロ法 ( 確率数値解析に於ける諸問題,VI) Author(s) 杉田, 洋 Citation 数理解析研究所講究録 (2004), 1351: 33-40 Issue Date 2004-01 URL http://hdlhandlenet/2433/64973 Right Type Departmental Bulletin Paper Textversion publisher Kyoto University
C^{*}$, 1351 2004 33-40 33 ( ) 1 ff, 1980, $\langle$,,,,,,,,,, ( ) $=$ $\vee,,,,,,, ( 1) ( ),,,,,,,, ( ),,,
34 2 $2^{\Omega}$ $\Omega$ $\Omega$,, $\Omega$, $\mathrm{e}$ $P$, Var $(\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{i}\iota\cdot)$ $X$, $X$ $X$, 1, $X$,,,, \sigma ( $X$ ),, 2 1 1 32 1,,, 1/32 $2^{10^{6}-5}$ $2^{10^{b}}$ 2 1, : $\{0, 1\}^{10^{6}}$ $\# A=2^{10^{\mathrm{G}}-5}$ 1 $\omega\in$ $\{0,1\}^{10^{6}}$, $\omega\not\in A$, $\omega\in A$, 1/32 1, 2 2,, 2,, 2, 1 $\omega\in$ $\{0,1\}^{10^{6}}$,, $\omega$, $\omega$, $\mathrm{e}$
$ $ P(g( 35 1 $\cdot n<l$ : 9: $\{0,1\}^{n}arrow\{0,1\}$ L (pseudorandom generator) $g$ (seed), $g(\omega )\in$ $\omega \in$ $\{0,1\}^{\prime \mathrm{t}}$ $[perp]$ $\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}\dot{)}$ $\{0,1\}^{L}$ (pseudo-random llulllbcib\neg, $g:$ $\}^{100}arrow\{0,1\}^{10^{6}}$ 2 $\omega \in$, $\}^{101?}$ 1 $\{$0,1, $g$ (\mbox{\boldmath $\omega$} ), $g(\omega )\not\in A$, $g(\omega )\in A$, $g$ 2, ( ) $P(g(\omega )\in A)$ $P(g(\omega )\in A)$,$\cdot$ 2,, 2, $P(\omega\in A)=P(g(\omega )\in A)$, \sim 1 $g:$ $\{0,1\}^{n}arrow\{0,1\}^{L}$ 1,, $\mathrm{m}$- (cf [1, 4]), $500\sim 10^{4}$,, 2, \acute,,, $\omega \in$ $\{0,1\}^{n}$ 3 $\{0,1\}^{n}arrow\{\mathrm{O}, $g:$ 1\}$L $A\subseteq$ $\{0,1\}^{\Gamma_{d}}$ $\omega )\in A$ ) $-P(\omega\in\Lambda) $, $g$, $g$ $\lceil g(\omega )$, 2 JIS[2],, : $n\in \mathrm{n}$ 1,,, 2,
$\cdot 2^{1\mathit{0}^{6}-\mathrm{S}}$ $2^{10^{\grave{\mathrm{b}}}}$ 36 (i) (, ) $\omega $ (ii) $g$ $g(\omega )$,, (iii), 9,, (i), (ii) $P(g(\mathrm{d})\in A)$ (iii) $\vee C$ $P(\omega\in A)$, $g$, $g$ $A:=g(\{0,1\}^{n})\subset\{0,1\}^{L}$ (1), $P(\omega\in A)\leq 2^{n-L}<P(g(\omega )\in A)=1$, $g$, 31 2, $g$ : 10 $\{0,1\}^{100}arrow\{0,1\}$ ( 1/32) 2 $2^{10^{6}}$ $2^{10^{0}-5}$, ${}_{32rr}C$ $=$ $ \cdot\frac{32^{j};\cdot(32^{t};\cdot-1)(32r-2)\mathrm{x}\cdot\cdot \mathrm{x}(32r\cdot-\prime r+1)}{r!} $, $\prime r=2^{10^{6}-5}$ $>$ $\frac{(31r)^{r}}{r!}\sim,\cdot\frac{(31\prime r)^{\mathrm{r}}}{1re^{-\mathrm{r}}\sqrt{2\pi\prime r}}=(31e,)^{r}/\sqrt{2\pi r}>(30e)^{\mathrm{r}}>2^{6r}$, $\omega\in A$, $2^{6\cdot 2^{10^{6}-5}}$,,, 6, $L$ r, $2^{L}$ $\cdot$ 6 ( ),,,
37 ( ),,, ( ), ( ) $[3, 5]$ $\mathrm{p}\neq \mathrm{n}\mathrm{p}$,,,,, [9] 3 $\mathrm{m}$- (cf [1, 4]) (1), M- $x_{n}:=f(x_{n-p}, x_{n-p+1}, \ldots,x_{n-1})$, $L>p$ $A:=\{\omega=(\omega_{1},\omega 2,, \omega L)\in\{0,1\}^{L} ; \omega_{p+}1-f(\omega_{1},\omega 2,, \omega_{\mathrm{p}})=0\}$ $f$ $\omega\in A$ M-, 32 ( ) $Z$ $m$, $\{0, 1\}^{m}$, $\{Z_{n}\}_{n=1}^{N}$ $X$ $X$ $Nm$, $X( \omega):=\frac{1}{n}\sum_{n=1}^{n}z_{n}(\omega_{n})$, $\omega_{n}\in\{0,1\}_{:}^{m}$ $\omega=(\omega_{1}$,, $\omega_{n})\in\{0,1\}^{nm}$, $X$ $\mathrm{e}[x]=\mathrm{e}[z]$ $Z$ Var[X] $=\mathrm{v}\mathrm{a}\mathrm{r}[z]/n$ $P( X- \mathrm{e}[\prime Z] >\delta)<\frac{\mathrm{v}\mathrm{a}\mathrm{r}[z]}{n\delta^{2}}$ 3, $A:=\{\omega\in \{0,1\}^{Nm} ; X(\omega)-\mathrm{E}[Z] >\delta\}$ (2) $3\mathrm{E}[X]$ Var[X] Var[X] ( $X$ ),
38, $\omega\in$ $\{0,1\}^{Nm}$ $\omega\not\in A$, $\omega\in A$, ( $P(\omega\in A)$ ) $[\prime Z]/(N\delta^{\mathit{2}})$, $P(\omega\in A)<$, $\mathrm{e}[x]$ 4, $P(\omega\in A)$,, $\mathrm{a}\mathrm{a}$ $[searrow]$,, 1 (cf [3]) $N\leq 2^{m}$, $g:$ $\{0,1\}^{2m}arrow$ $\{0,1\}^{Nm}$ : $\mathrm{e}[x(g(\omega ))]=\mathrm{e}[x(\omega)]$, Var[X $(g(\omega ))$ ] $=$ Var[X $(\omega)$] $\omega$ $\omega$ $\{0, 1\}^{Nm}$ $\{0, 1\}^{2m}$ $)$ 1 $g$ $X(g$ (\mbox{\boldmath $\omega$} ) $\mathrm{e}[z]$, $P( X(g( \omega ))-\mathrm{e}[z] >\delta)<\frac{\mathrm{v}\mathrm{a}\mathrm{r}[z]}{n\delta^{2}}$, (2), $P(g(\omega )\in A)<\mathrm{V}$ $[Z]/(N\delta^{\mathit{2}})$ $X$ (\mbox{\boldmath $\omega$}), 9 $X$ : $\mathrm{g}\mathrm{f}(2^{m})$ $2^{m}$ 1 $g$, $\phi$ 2 $\mathrm{g}\mathrm{f}(2^{m})arrow\{0,1\}^{m}$ $\psi$ $\mathrm{g}\mathrm{f}(2^{\pi\iota})arrow\{1,2,, 2^{m}\}$ : : $\omega :=(x, \alpha)\in$ $\{0,1\}^{m}\mathrm{x}$ $\{0,1\}^{m}\cong$ $\{0,1\}^{2m}$, $Z_{n}(\omega ):=\phi[\phi^{-1}x+(\psi^{-1}n)(\phi^{-1}\alpha)]$, $n=1,2,$ $\ldots,$ $2^{2m}$ $g(\omega ):=(Z_{1}(\omega ), Z_{2}(\omega ),$, $Z_{N}(\omega ))\in\{0,1\}^{nm}$ $\omega $, $\{0, 1\}^{2m}$, $\{Z_{n}(\omega )\}_{n=1}^{2^{m}}$,, $a,$ $1\leq n<n \leq 2^{7n}$ $Z_{n}(\omega )$ $\{0, 1\}^{m}$ $b\in$ $\{0,1\}^{m}$, $P(Z_{n}(\omega )=a, Z_{n }(\omega )=b)$ $=P$ ( a, n $\phi^{-1}x+(\psi^{-1}n)(\phi^{-1}\alpha)=\phi$ $\phi^{-1}x+(\psi^{-1}$ $ $ ) ( b) $\phi^{-1}\alpha)=\phi$
9031 $\mathrm{a}\mathrm{r}\mathrm{b}\mathrm{o}\mathrm{r}/\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{n}/$ Washington,DC, 38, $(x, \alpha )$ $\mathrm{g}\mathrm{f}(2^{m})$ 1 $\{$ $x +$ ( $\psi^{-1}$ n) $\alpha $ $x +$ ( $\psi^{-1}$ n $ $ $\alpha $ ) $=$ $\phi$a $=$ $\phi$ b $(x_{0}, \alpha_{0} )\in \mathrm{g}\mathrm{f}(2^{m})\mathrm{x}\mathrm{g}\mathrm{f}(2^{m})$ $P(Z_{n}(\omega )=a, Z_{n }(\omega )=b)$ $=$ $P(\{(\phi^{-1}x_{0}, \phi^{-1}\alpha_{0} )\})$ $=$ $2^{-2m}$ $=$ $P(Z_{n}(\omega )=a)p(z_{n }(\omega )=b)$ 1 qed 5 1 $g$ $\{0, 1\}^{2m}$ $2m$ 1, $g$,, $[6, 11]$, ( ) $[7, 8]$ 6,,,,,, [1],,, (1989) [2] JIS $\mathrm{z}$,, 2001 [3] M Luby, Pseudorandmness and cryptographic applications, Princeton Computer Science Notes, Princeton University Press, (1996) [4] M Matsumoto and T Nishimura, Mersenne twister: a 623-dimension\sim \sim y equidis tributed uniform pseudo random number generator, ACM, Trams Model Comput Simul, &1, (1998) 3-30 [5] $\mathrm{d}\mathrm{r}$ $\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{n}/\mathrm{a}\mathrm{n}\mathrm{n}$ Stinson, Cryptography (Theory and practice), CRC Press, Boca (1995) [6] H Sugita, Robust numerical integration and pairwise independent randoui variables, Jour Comput Appl Math, 139 (2002), 1-8
mac Publ 40 [7] H Sugita, Dynamic random Weyl sampling for drastic reduction of randomness in Monte Carlo integration, Math Comput Simulation, 62 (2003), 529-537 [8],, 56-1, (2004) [9] H Sugita, An analytic approach to secure pseudo random generation, peprint [10] H Sugita, The Random Sampler, C/C+, : $//\mathrm{i}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{k}$ $\mathrm{i}\mathrm{c}/\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}/\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{s}$ ht tp: html $\mathrm{c}\mathrm{o}\mathrm{m}/\mathrm{h}\mathrm{i}\mathrm{r}\mathrm{o}\mathrm{s}\mathrm{h}\mathrm{i}_{-}\mathrm{s}\mathrm{u}\mathrm{g}\mathrm{i}\mathrm{t}\mathrm{a}/$ [11] H Sugita and S Takanobu, Random Weyl sampling for robust numerical integration of complicated functions, Monte Carlo Methods and Appl, 6-1 (1999), 27-48