整数ロジスティック写像を用いた 　　　　　乱数生成法とその応用

　　 整数ロジスティック写像を用いた 　　　　　乱数生成法とその応用

　　　　　　　　　董　際国

　電気通信大学大学院情報システム学研究科 　　　　博士（工学）の学位申請論文

　　　　　　　　　 2012 ^年 3 ^月

　　　整数ロジスティック写像を用いた 　　　　　乱数生成法とその応用

　　　　　　　　博士論文審査委員会

　　　　　　主査　森田　啓義　教授

　　　　　　委員　田中　健次　教授

　　　　　　委員　小池　英樹　教授

　　　　　　委員　長岡　浩司　教授

　　　　　　委員　多田　好克　教授

　　　　　　　著作権所有者

　　　　　　　 　　董　際国

　　　　　　　 　　　 2012 ^年

　　　 Random Numbers Generation Method 　　 and The Application By Integer Logistic Map

　　　　　 　　 DONG JIGUO

　　　　　 　　　 Abstract

In this paper, we propose a method for calculate a logistic map: x_t+1 = 4x_t(1−x_t) by using the integer type, and, apply the method to generate random numbers. The paper is composed by Chapter 6.

In Chapter 2, we prepare a basic concept and the term concerning the chaos needed since Chapter 3. Moreover, we introduce a past research and the trait of the computational method that uses the integer operation used with this paper.

In Chapter 3, we confirm the character of an initial sensitive value etc. of the logistic map operated by the integer type. We propose the method of examining the time series that falls into the given value including the fixed point. And, we give the approximate relations between the calculation accuracy and the state length of non-cycle.

In Chapter 4, we calculate a logistic map of arbitrary calculation accuracy(N- bits) by integer operation, and, we propose a random number generation method based on the mixing operation using an internal state of the 2N-bits that existed in the calculation process. Moreover, we compare sensitive on initial conditions by the speed of settling of Hamming Distance for the generated random number sequence with the proposal method and well-known Mersenne Twister. And, we examined statistical testing binary numbers generated with calculation accuracy N = 128, and conclude that these binary numbers are uniformly distributed.

In Chapter 5, we propose a method of generating random number sequences which are suitable not only for producing a huge amount of IDs and passwords

but also for placing them under control. We generate a binary random sequence with an initial valueRand a coordinates ofK dimensional space to represent the index i. The ith random numberR_i is generated byK−1 times iterations with the initial value R. We investigate the performance of the multi-dimensional random number generation and show that can generate computationally secure key values in case of using the logistic map as a random number generator.

The result of this research can contribute to a more low-cost, higher attesta- tion of security and the construction of the cryptosystem.

　　　　整数ロジスティック写像を用いた 　　　　　　　乱数生成法とその応用

　　　　　 　　　　董　際国

　　　　　 　　　　 概　要

カオスの研究は，約100年前（ポアンカレ）からとされ，1970年代から盛ん になり，多くの成果を得るようになった．「カオスの最大の応用は擬似乱数にあ る」と言われるほどカオスの擬似乱数生成への応用が高く期待されている．そ の中，カオスを生成する関数で，ほとんどのカオスの入門書に紹介されている ロジスティック写像xt+1 = 4xt(1−xt)に対する研究成果が多く発表されている．

しかし，カオスに関する理論的な研究成果が多く得られているにもかかわらず，

幅広く産業技術としてのカオスの応用システムはまだ見られていないのが現状 である．

ほとんどのカオスに関する研究は，実数で定義，計算されるカオス時系列の 性質に対するものに対し，産業技術としてのカオスの応用は多くの場合，有理 数（コンピュータ）で計算されている．実数の計算で得られるカオス時系列の 性質は，必ずしも有理数の計算で得られる時系列が有する性質と一致するとは 限らない，むしろ，基本性質は異なっていることは一般的であろうと考えられ る．有限計算精度で生成した時系列はいずれ周期に落ち入るため，原理的には カオスにならない，擬似カオスと称される．従って，カオスを産業技術へ利用 するには，まず有限計算精度の計算で得られる時系列が有する性質を解明する 必要がある．

カオスを産業技術として応用するとき，多くの場合に同じ入力に対し同じ安 定した出力が求められる．このような再現性を持つ比較的に安価なシステムは デジタル（コンピュータ）システムである．カオスは実数で定義されている．コ

ンピュータでの無理数の計算は近似計算で浮動小数点演算法を用いる．しかし，

安価な産業用計算機（マイクロコントローラ）は浮動小数点をサポートしてい ない．また，浮動小数点演算はシステムの種類によって，異なる規格を採用し ていることがある．このことは，異なるシステム（規格）において，同じ入力 で同じ出力がえられない可能性があることを意味する．従って，浮動小数点演 算によるカオスの計算を含むシステムでは安価なシステムになり難い．そのた め，異なるシステムでも同じ入力に対し同じ出力が得られる整数演算による擬 似カオス時系列の生成が求められる．

ロジスティック写像による乱数生成について，1947年にも2進計算機の原型 を考案したフォン・ノイマンらにより提案された．しかし，ロジスティック写像 を計算して得られる時系列は一様分布とはならず，Ｕ字型となっている．それ を使って，一様分布の系列にするには何らかの処理が必要である．しかし，こ れまでの提案された方法では何れも大幅な生成速度の低下を伴っている．また，

計算精度ビット長が長くすることで，生成される系列の周期長を長くすること ができるが，写像速度の低下に繋がる．一方，周期長，統計的乱数性，生成速 度などは乱数生成法においての重要な指標となっている．従って，計算精度拡 張の高速な計算方法，乱数生成速度の低下が小さい処理方法が望まれる．

本研究はロジスティック写像を擬似乱数生成へ応用することを考える．本研 究は序章と終章を含み，6章からなる．以下，2から5の各章の概要を述べる．

2章では，3章以降で必要となるカオスに関する基礎的な概念・用語を準備す る．とくに，本論分の主要結果であるロジスティック写像の計算機上での演算に ついて，従来用いられてきた浮動小数点法による計算方法と比較しながら，本 論文で提案する整数演算を用いた計算方法の特色について論じる．

3章では，まず，整数ロジスティック写像において，初期値敏感性を示さない 場合すなわち，ホール（Hall）の存在を明らかにする．また，初期値が不動点以 外の値で，有限回の繰り返し計算で不動点に入ることを回避するために，不動 点を含む任意の値に落ち入る系列の存在を調べる方法を提案する．そして，数 値計算により，整数ロジスティック写像が生成できる平均的な非周期状態長の 推定値と計算精度N との近似的な関係を与える．

4章では，整数演算を用いて計算精度Nビットのロジスティック写像を計算 し，計算過程に存在する2Nビットの内部状態を利用した撹拌方法に基づく擬似

乱数生成法を提案する．また，生成した乱数列に対し，初期値敏感性をハミン グ距離の収束の速さで提案法とMTと比較を行い，提案法の効果を示した．そ して，計算精度N = 128ビットで生成される2進数列に対し，統計的検定を行 い，一様性を持つとの結論を得た．

5章では，大量のID・パスワード（PW）の生成だけでなく，管理にも適した 擬似乱数列の生成方法を提案する．提案法は，初期値(種)RとK次元空間座標 で表す位置iを用いて2値系列を生成する．i番目の擬似乱数列R_iは初期値R を用いてK −1回繰り返して生成される．擬似乱数生成がロジスティック写像 を用いたとき，提案方式における多次元乱数生成の性能を確認し，計算量的に 安全なキーの生成が可能であることを示す．

その結果，本研究は整数で演算するロジスティック写像が有する基本的な性 質を解明して，ロジスティック写像をセキュリティー用乱数生成へ応用すると き，初期値選びや計算精度長の決定の根拠を与え，安全な乱数生成システムの 構築を可能にした（3章）．そして，高速な乱数生成方法を提案し（4章），こ れまで実現困難とされるキーの使い捨て暗号や認証を容易にした（5章）．

目 次

第1章 序章 1

1.1 はじめに . . . 1

1.1.1 カオスの研究に期待されること . . . 1

1.1.2 カオスとデジタルコンピュータ . . . 2

1.2 本研究の目的 . . . 4

1.2.1 秩序の解明 . . . 4

1.2.2 擬似乱数生成への応用 . . . 5

1.3 本研究の構成 . . . 6

第2章 整数を用いたロジスティック写像の計算 7 2.1 はじめに . . . 8

2.2 ロジスティック写像の特徴 . . . 10

2.3 浮動小数点と固定小数点によるロジスティック写像の計算について 13 2.4 整数ロジスティック写像 . . . 16

2.4.1 背景 . . . 16

2.4.2 定義 . . . 16

2.4.3 整数ロジスティック写像 . . . 17

2.5 まとめ . . . 19

第3章 発散，収束，周期性 20 3.1 はじめに . . . 21

3.2 発散 . . . 23

3.2.1 目的 . . . 23

3.2.2 準備 . . . 23

3.2.3 ホールの存在範囲とその大きさ . . . 26

3.3 収束 . . . 32

3.3.1 目的 . . . 32

3.3.2 準備 . . . 32

3.3.3 ロジスティック写像の逆軌道 . . . 33

3.3.4 整数ロジスティック写像の逆軌道 . . . 34

3.3.5 不動点に至る全軌道の列挙 . . . 37

3.4 整数ロジスティック写像の周期性 . . . 39

3.4.1 異なるループの数 . . . 39

3.4.2 初期値とループの関係 . . . 41

3.4.3 非周期状態長 . . . 42

3.5 まとめ . . . 47

第4章 整数ロジスティック写像と撹拌演算による乱数生成 48 4.1 はじめに . . . 49

4.2 乱数の生成――撹拌 . . . 51

4.3 提案法の効果 . . . 56

4.3.1 多重化しなくても良質な擬似乱数を生成可能 . . . 56

4.3.2 生成速度 . . . 57

4.3.3 初期状態の微小な差に対する敏感な反応 . . . 57

4.4 統計的検定 . . . 61

4.4.1 検定方法 . . . 61

4.4.2 検定結果 . . . 62

4.4.3 検定結果について . . . 67

4.5 まとめ . . . 69

第5章 認証キーの生成・管理のための「多次元インデックス法」の提案 70 5.1 はじめに . . . 71

5.2 多次元インデックス法 . . . 73

5.2.1 「多次元インデックス法」に適用する乱数生成器G_Nの必 要条件 . . . 73

5.2.2 一次元インデックス法 . . . 74

5.2.3 二次元インデックス法 . . . 75

5.2.4 多次元インデックス法 . . . 78

5.3 評価 . . . 79

5.3.1 生成速度 . . . 79

5.3.2 初期値敏感性の確認 . . . 81

5.3.3 近傍座標i間のR_iの無相関性 . . . 82

5.3.4 非周期空間サイズ . . . 83

5.3.5 パラメータN, M, K(k)について. . . 84

5.4 安全性 . . . 85

5.4.1 整数ロジスティック写像の特徴 . . . 85

5.4.2 安全のための実装 . . . 86

5.4.3 安全性について . . . 88

5.5 提案法を用いたキー管理法 . . . 89

5.5.1 システムの構成の一例 . . . 89

5.5.2 認証用コードの管理 . . . 90

5.5.3 暗号鍵の管理 . . . 92

5.6 まとめ . . . 93

第6章 終章 94 6.1 結論 . . . 94

6.2 今後の課題 . . . 97

6.2.1 乱数生成法の応用 . . . 97

6.2.2 逆対応の計算の利用 . . . 97

付 録A 多倍長整数ロジスティック写像の計算 99 A.1 2^m進数の整数ロジスティック写像の計算 . . . 99

A.1.1 既存の計算システムの計算能力 . . . 99

A.1.2 計算能力に応じた分割計算 . . . 99

A.1.3 整数の分割演算を用いたロジスティック写像の計算 . . . 100

付 録B 発散と収束の観測 102 B.1 整数ロジスティック写像とその逆対応 . . . 102

B.2 発散：初期値敏感性 . . . 103

B.2.1 有限計算精度での数値 . . . 103

B.2.2 初期状態の微差と丸め誤差のカオス軌道への影響 . . . . 103

B.2.3 初期値敏感性と有限計算精度のカオス軌道 . . . 104

B.3 収束 . . . 108

B.3.1 整数ロジスティック写像の逆軌道と順軌道 . . . 108

B.3.2 逆計算による順計算の軌道への収束 . . . 111

付 録C 周期性 114 C.1 計算精度Nと最大推定リーダー長`⁰及び主な周期長 . . . 115

C.2 初期値とループの関係 . . . 117

　 参考文献　　　　　　　 121

謝辞　　　　　　　125

関連論文の印刷公表の方法及び時期　　　　　　　126

著者略歴　　　　　　　 127

図 目 次

2.1 ロジスティック写像xt+1 = 4xt(1−xt)の規則と不規則． . . . . 10

2.2 ロジスティック写像x_t+1 = 4x_t(1−x_t)から生成したx_tの分布． 12 2.3 ループとリーダー . . . 18

3.1 整数ロジスティック写像の状態X_tの推移．. . . 31

3.2 計算精度N = 128ビットで得られた∆X_t=X_t−X˜_tの頻度分布． 35 3.3 計算精度N = 128ビットの不動点C0· · ·0への軌跡． . . . 38

3.4 計算精度N = 18∼72，調べ得たループ数． . . . 40

3.5 計算精度N = 18,22,26,30で，区間[1,2^N−1−1]を16区域に分 割して調べ得た最頻度のループの頻度． . . . 41

3.6 計算精度N = 30で，(a)は区間[1,3276800]を，そして(b)は [1,25600]をそれぞれ50等間隔に分割して調べ得た最頻度のルー プの頻度． . . . 42

3.7 計算精度と平均リーダー長`の関係． . . . 45

3.8 最長周期長(a)，最多周期長(b)と計算精度Nの関係． . . . 46

4.1 整数乗算の2進展開. . . 53

4.2 ハミング距離の推移の比較 . . . 59

5.1 キーの一次元配置 . . . 76

5.2 キーの二次元配置 . . . 77

5.3 安全のための実装例（k = 1）. . . 87

5.4 多次元キー生成・管理 . . . 89

A.1 入力16ビット，出力32ビットの乗算器による16ビット×16ビッ トの整数の乗算の分割演算による式(A.1)の計算精度64ビット のc言語のソースコードの一例． . . . 101

表 目 次

3.1 f0，d₋，d+とf₀⁽ⁱ⁾，d⁽ⁱ⁾₋，d⁽ⁱ⁾₊ の最大最小値 . . . 36

3.2 N とX = 3×2^N−2に至る可能なXの数N_S，軌道数N_O及びT 38 3.3 計算精度Nとループ数 . . . 39

3.4 計算精度N = 18∼72において，用いた初期値の数M . . . 40

4.1 提案法とMTの連検定と組み合わせ検定の結果 . . . 57

4.2 計算精度と乱数生成速度 . . . 57

4.3 等分布検定の結果 . . . 62

4.4 シリアル検定の結果 . . . 63

4.5 ポーカー検定の結果 . . . 64

4.6 クーポン券収集検定の結果 . . . 64

4.7 連検定の結果 . . . 65

4.8 衝突検定の結果 . . . 66

4.9 誕生日間隔検定の結果 . . . 66

4.10 シリアル相関検定結果 . . . 67

4.11 MTと物理乱数IDQの衝突検定の結果 . . . 68

5.1 キーの生成時間の比較(Unit: msec) . . . 80

5.2 ハミング距離の頻度のχ二乗分布（R_i, R⁰_i） . . . 82

5.3 ハミング距離の頻度のχ二乗分布（Ri, Ri⁰） . . . 83

5.4 計算精度と非周期空間サイズ . . . 83

5.5 リモコンキーの使い捨て認証コードの生成・管理 . . . 91

B.1 丸め誤差を分離した初期値敏感性の観測．整数ロジスティック写 像を整数を用いた固定小数点演算128ビットで初期値X₀から計 算し，t= 0 ∼63のX_tを示す．X_tは16進数32桁で表示．. . . 106

B.2 異なる初期状態(値)による初期値敏感性による発散の強さ．整 数ロジスティック写像を整数を用いた固定小数点演算64ビット で初期値X₀から計算し，t = 0∼63のX_tを示す．X_tは16進数 16桁で表示． . . . 107 B.3 整数ロジスティック写像の順軌道と逆軌道．X_tは整数を用いた

固定小数点演算128ビットで計算し，16進数32桁で表示．次の ページへ続き . . . 109 B.4 整数ロジスティック写像の逆軌道の順軌道への収束．X_tとX˜_tは

逆計算（tが小さくなる）に従って，上位桁の一致が多くなるこ とが観察される．X_tは固定小数点演算128ビット，16進数32桁 で表示．次のページへ続き . . . 112 C.1 整数ロジスティック写像を計算精度33 ∼75ビットで数値計算に

よる周期性についての結果． . . . 116 C.2 計算精度Nを18ビット(a)，22ビット(b)，26ビット(c)，30ビッ

ト(d)の区間[1,2^N−1−1]で，整数ロジスティック写像が取り得 る全ての初期値に対し，16等間隔分割して数値実験で調べ，得 られたループの頻度． . . . 118 C.3 計算精度30ビットの整数ロジスティック写像の小域分割による

ループの頻度． . . . 119

第 1 ^{章 序章}

1.1 ^はじめに

カオスは，気象のような時間とともに複雑に変化する現象，すなわち，時間 とともに不規則的に変化する現象，また，比較的簡単な規則に支配された不規 則振動を指すが，統一した定義はまだできていない[1]．

カオス研究は数理と現象との２つの側面を持つ．微分方程式（差分方程式）

から生成する時系列データが有する性質を解析し明らかにすることと，自然現 象を観測してえられる時系列データからその自然現象の背後にある規則（関数）

を見出す（同定する）ことである．

カオス研究の源流はポアンカレが100年も前の天体力学における3体問題の 研究にカオスの存在に気付いたことからとされている．しかし，カオス研究が 盛んになり，多くの成果を得るようになったのは，Li-Yorkeらが1975年に発表 した有名な論文“Period Three Implies Chaos”以来とも言われる．それはデジ タルコンピュータの計算能力の発展によるものに他ならない[2]．

それから今，カオスに対し数理的な研究と実験による研究が多くなされて，そ の数理的な性質と多くのカオス的な現象が観察され，カオスに対する理解のみ ならず，その応用に対する期待も高まっている．

1.1.1 カオスの研究に期待されること

カオスの研究で多くの数理的な特性の解明と実験による研究成果を得たこと で，カオスは多くの分野への応用が期待されている．それらの多くの分野への 応用は，現象（時系列データ）からその関数（背後に潜む規則）の同定と関数

（装置）によるカオス（現象となる時系列データ）の生成にまとめられる．いず れの場合もカオスを生成する関数モデルが必要となる．

本研究は，カオスを生成するロジスティック写像を実用化した整数ロジスティッ

第1章 序章

ク写像を計算して，工学への応用を考える．

1.1.2 カオスとデジタルコンピュータ

カオスの理論研究と実験的研究はコンピュータ技術の発展により，発展を成 し遂げた．コンピュータの計算（データ処理）能力の高まりで，カオスの特徴

（窓，熊の手，奇妙なアトラクタなど[1,2]）の可視化ができ，本来混沌となるカ オスが持つ秩序を見ることが可能になった．

これからのカオスの応用も，コンピュータは欠かせない．まず，自然や人工 装置からのカオス的な振る舞いをする時系列データから，その背後に潜む関数

（モデル）を同定するのにコンピュータを利用した解析が必要となる．また，カ オスを産業技術として応用するとき，多くの場合に同じ入力に対し同じ安定し た出力が求められる．このような再現性を持つ比較的に安価なシステムはデジ タル（コンピュータ）システムである．

実際，カオス関数を計算して，カオスを生成するためには，デジタルコンピュー タが用いられる．しかし，デジタルコンピュータで生成したカオス系列は，有 限計算精度であるため，原理的に真のカオスとはならない．一般に擬似カオス と称される．

時系列データから関数モデルを同定する場合，現象や装置から採取（観測）

したデータは，観測精度が有限であるため，観測誤差を含む．こうして同定さ れた関数モデルは真の関数モデルとはならず，誤差を含む近似モデルしかなら ない．従って，このような近似モデルを用いて，カオス時系列を生成するとき，

生成した時系列は元の（現象）カオス時系列とはならなく，別の系列となる．

一方，アナログ回路によるカオス生成の試みもなされている[2]．この方法で は，コンピュータの有限計算精度の欠点を回避できるが，アナログ回路におい ての状態決定精度に比べ，コンピュータの状態決定精度は遥かに高い[4]．また，

アナログ回路は入出力の再現性は保証できない問題が残る．入出力の再現性は ほとんどの産業技術に求められ，特に，試験段階に必要とされる．

カオス（関数）に対する数理的な研究では無限計算精度で行われているのに 対し，応用では関数を計算してカオス（時系列）の生成はデジタルコンピュー タを用いて，有限計算精度で行われている．有限計算精度でカオスを計算する とき，現れる発散（初期値敏感性）や周期性は，桁数や演算方法によって，現

1.1. はじめに 象が異なるので，理論だけでは詳しく論じられない．すなわち，研究と応用に おいての条件の不一致が生じる．

こうしてコンピュータを用いて生成した擬似カオス時系列は，必ずしも無限 計算精度の数理的研究で得られた性質と同じとは限らない．むしろ，その性質 は異なっていると考えたほうが一般的である．従って，数理的研究で得られた カオス研究の成果はそのまま応用に利用することはできず，有限計算精度で計 算して検証する必要がある．

カオスは実数で定義されている．コンピュータでの無理数の計算は近似計算 で浮動小数点演算法を用いる．しかし，安価な産業用計算機（マイクロコント ローラ）は浮動小数点をサポートしていない．また，浮動小数点演算はシステ ムの種類によって，異なる規格を採用していることがある．このことは，異な るシステムにおいて，同じ入力で同じ出力がえられない可能性があることを意 味する．従って，浮動小数点演算によるカオスの計算を含むシステムでは安価 なシステムになり難い．

デジタルコンピュータは真のカオスを生成できない．一方，産業技術は，物

（製品）として具体化され，物は寿命を持つ．すなわち，産業技術は無限を扱え ない，無限を必要としない．また，有限計算精度でのカオスの計算は，無限の 精度の計算過程に計算精度相当の桁に乱れが加わったことに等しい．このよう なカオス＋小さな乱れの系は本来は決定論的で定まるカオスを，実質的には非 決定論的存在としてしまうのである[1]．こうして，カオスの最大の応用は擬似 乱数である[3]とも言われ，カオス応用の可能性はまだ残されている．

第1章 序章

1.2 ^{本研究の目的}

本研究はカオスの産業への応用を前提としている．カオスを生成する関数は，

いくつも知られており[2]，それらは，無限長の周期を有するや初期状態の違い に敏感に反応する，といった応用上重要な特性を持つ．しかし，個々のカオス 関数は固有の性質を持つ．そのため，与えられた条件の下での該当カオス関数 特有の性質を解明，理解する必要がある．

本研究では，カオス関数の中でも最も簡単な関数，ロジスティック写像

`: [0,1]→[0,1];

`(x) =rx(1−x)

において，r= 4の場合を対象とする．以下では，r= 4のロジスティック写像 を単にロジスティック写像と呼ぶ．ロジスティック写像についてはこれまでに数 多くの論文や研究報告があり，それらの知見が利用可能であること，また，カ オスの工学への応用を考える場合，ロジスティック写像は簡単な固定小数点演 算で計算できるという利点を有することによる．

1.2.1 秩序の解明

有限計算精度でロジスティック写像を繰返し計算する場合，初期値によっては，

発散しない場合がある．これらの初期値の集まりを本論文ではホール（Hall）と 呼ぶ．本論文の最大の目的である擬似乱数生成を考えるとき，ホールの存在を 明らかにする必要がある．

ロジスティック写像では，例えば，初期値が0,0.25,0.75,1以外の値であって も，有限回の繰り返しで0,0.75に落ち入ることがある．ロジスティック写像に 0.75を入力すると同じ0.75が出力される．このような値は不動点という．とこ ろが，有限計算精度でロジスティック写像を計算する場合は，この性質は自明 ではない．つまり，どのような初期値の場合に，何回の繰り返しで不動点に落 ち入るかを求めるためには，与えられた演算精度の下で，実際に数値計算する ほかに手立てがない．本研究は，ロジスティック写像の逆対応を利用して，不 動点に入ることを回避するために，不動点を含む任意の値に到達する初期値が 存在するかどうかを調べる方法について考案する．

1.2. 本研究の目的 周期に落ち入る前の部分と周期長は，生成できる非周期状態の擬似乱数の長 さを決める．本論文では，数値計算により，整数ロジスティック写像が生成で きる平均的な非周期的な状態の長さの推定値と計算精度Nとの近似的な関係を 示す．（第3章）．

1.2.2 ^{擬似乱数生成への応用}

有限計算精度でのカオスの計算は，カオスの最大の応用は擬似乱数であると いわれるように，従来の線形合同法を代表とする擬似乱数生成法と違い，非線 形性や初期状態の違いをより敏感に発散するといった性質を有する．本研究の もう一つの目的は，有限計算精度で計算されるロジスティック写像の時系列を 解析することによって得られた成果を活かして，ロジスティック写像を擬似乱 数生成に応用することである（第4章，第5章）．

第1章 序章

1.3 ^{本研究の構成}

本研究は6章からなる．序章に続き，2章では3章以降で必要となるカオスに 関する基礎的な概念・用語を準備する．また，本論文で用いる整数演算を用い た計算方法についての従来の研究やその特色について，紹介する．

これまでの研究において，整数演算で得られた系列に対する調査結果では，

得られた周期長や周期に落ち入る前の長さの平均は周期長に関する頻度分布を 考慮していない．任意に初期値を選ぶ場合に，頻度分布の高い周期に落ち入る 系列になる可能性が高いため，仮に短い周期長の頻度分布が高い場合，周期長 の短い系列が生成される可能性が高くなる．また，初期値が不動点以外の値で，

有限回の繰り返しで不動点に落ち入る場合についての対応方法と，有限計算精 度でカオスを計算するときに現れる初期状態の違いを発散しない場合について の議論は，あまりなされていない．これらのことは，ロジスティック写像を乱 数生成へ応用するときに，重要である．

3章では整数ロジスティック写像が有する発散の性質などを確認する．また，

不動点に入ることを回避するために，不動点を含む任意の値に落ち入る系列の 存在を調べる方法を提案する．そして，整数ロジスティック写像の周期性を観 察し，周期長に関する頻度分布を考慮した計算精度と平均的な非周期状態長の 推定値との間の近似的な関係を与える．

4章では計算精度N ビットの整数ロジスティック写像を計算し，計算過程に 存在する2N ビットの内部状態を利用した撹拌方法に基づく擬似乱数生成法を 提案する．

5章では認証，識別用ID・パスワード（PW）の管理に適した一定の長さの 擬似乱数列の生成方法を提案する．

最後に6章では結論と今後の課題について述べる．

第 2 ^章 整数を用いたロジスティック 写像の計算

概要 本章では3章以降で必要となるカオスに関する基礎的な概 念・用語を準備する．とくに，本論文の主要結果であるロジスティッ ク写像の計算機上での演算について，従来用いられてきた浮動小数 点法による計算方法と比較しながら，本論文で提案する整数演算を 用いた計算方法の特色について論じる．

第2章 整数を用いたロジスティック写像の計算

2.1 ^はじめに

カオスを生成する関数は数多く紹介されている[1-3]．その中，ロジスティッ ク写像は最も単純なカオスを生成する関数として，カオスに関する入門書や教 科書には必ずといっていいほど紹介されている[1-4]．本研究では，このロジス ティック写像に焦点をあてて論じていく．ロジスティック写像は，0< r≤4に 対して一般に，

` : [0,1]→[0,1]

`(x) =rx(1−x) と定義される．この写像を用いて，差分方程式

⎧⎪

⎨

⎪⎩

x₀ = 0以上，1以下の任意の小数 xt+1 = rxt(1−xt), t≥0, 0< r≤4

(2.1)

で生成され定まる数列{x_t}は，0.35699456· · ·< r≤4の範囲で，特定の周期を 持たない不規則な変化をすることが知られている．本研究は式(2.1)において，

r = 4とおいた

⎧⎪

⎨

⎪⎩

x₀ = 0より大，1より小の任意の小数 x_t+1 = 4x_t(1−x_t), t≥0

(2.2)

のみを扱う．

式(2.2)に注目する理由は主に2つある．１つは，ロジスティック写像に関す

る論文や研究報告が数多く発表されていて，それらの知見が利用可能であるこ と[6-9,12-15,17-19]，もう1つは，ロジスティック写像は簡単な固定小数点（整 数）演算で計算できるため，乱数生成などへの応用が容易なことである．

擬似乱数数列を計算機により多量に作り出す試みは，現代の2進計算機の原 理を提案したフォン・ノイマン自身によって，計算機の誕生後まもなく始めら

れた[33]．式(2.2)を乱数生成に用いる試みは，簡単な2次方程式から複雑な系

列を生成できることで，1947年にフォン・ノイマンらによって始められた[6]．

2.1. はじめに 当時，カオスという言葉はまだ使われていないが，フォン・ノイマンは，早く も非線形関数による複雑な数列の生成に注目していた．また，浮動小数点演算 法もまだ一般に使われていない（[21] pp.212-214）．今日では実数に定義されて

いる式(2.2)の計算は浮動小数点演算が一般に用いられるが，式(2.2)の計算に

浮動小数点演算と固定小数点（整数）演算とどちらが有利かについての議論は 見当たらない．

応用技術として，有限計算精度の計算機でロジスティック写像を計算して時 系列を生成するとき，どのような計算方法を用いるかを注意深く吟味しておく 必要がある．考慮すべき点は２つある．

１つは同じ有限計算精度で，効率よくより長い周期長の系列が得られること，

もう1つはカオスとしてのロジスティック写像が持つ初期値敏感性である．

例として，有限計算精度で式(2.2) 初期値を８ビットの，x₀ = 0.01と0.02に 対する計算結果はそれぞれ

01→03→0F →3A→B5→D3 →93→FA→16 →. . . と

02→07→1E →6C→F9→17 →56→E4→61 →. . .

となる（ここに，x_tの小数点以下は16進表示である）．この下位ビットの違い は計算回数重ねると次第に拡大され，たちまち全く異なる時系列となる．この 初期値敏感性については次節で改めて説明する．

本章は以下のようになる．2節ではロジスティック写像の主な特徴を述べ，3 節では浮動小数点と固定小数点によるロジスティック写像の計算を比較して，同 じビット幅で得られる系列の周期長は浮動小数点法より固定小数点法の方が長 くなることを数値実験の結果から，固定小数点による計算がより有利であるこ とを示す．4節では整数ロジスティック写像について述べる．

第2章 整数を用いたロジスティック写像の計算

2.2 ロジスティック写像の特徴

この節ではロジスティック写像が持つ際立った特徴をまとめて説明する．こ れらの性質は，以降の章の議論で頻繁に用いられる．

不規則を支配する規則 最初に，128ビットのロジスティック写像を初期値を x0 =0.145C8AE2DD03ACEADD1A58869C17F73B(小数点以下16進表示) とおいて，固定小数点法で，繰り返し計算する．その結果，得られた時系列{x_t} より，対ξ_t= (x_t, x_t+1), t≥0を求め，これらを2次元平面上の点として，2000 点プロットした結果を図2.1に示す．固定小数点法を実際に行うには，整数の多 倍長演算を用いた．

図 2.1: ロジスティック写像x_t+1 = 4x_t(1−x_t)の規則と不規則．

2.2. ロジスティック写像の特徴 図2.1のt = 0∼15の点ξ_tを追って見ると，x_tの動きは不規則であるが，全 て一本の放物線上に乗っていることを確認できる．このことは比較的簡単な規 則に支配された不規則振動といわれる[1]．また，図2.1の放物線は直線x_t= 0.5 を対称軸として線対称である．すなわち，ある１つのx_t+1（縦軸）に対して，x_t として，２つの値がとり得る．言い換えると，x_tを知れば式(2.2)を用いてx_t+1 を計算できるが，xt+1を知っていてもxtを一意に決定することができない．

不動点 図2.1から，ロジスティック写像がxt = 0.75とxt = 0という不動点 が存在していることを確認できる．一旦，状態x_tが不動点に落ち入ると，それ 以降，繰り返し写像を計算しても，得られる状態x_tは全て同じとなる．ロジス ティック写像を計算して時系列を生成するとき，このような不動点に落ち入ら ないようにする必要がある．そのためには，初期値x₀として不動点を除外する だけでなく，不動点でない初期値から生成された時系列が不動点に落ち入るか どうかを知る必要がある．この問題については3章で詳しく論じる．

分布特性 ロジスティック写像は密度関数1/(πp

x(1−x))を持つことが知られ ている（[1] p.41）．例として，図2.2にロジスティック写像をT 回（T = 65536） 計算して出力した数列xt（1 ≤ t ≤ T）に対し，整数bxt×256cの系列の頻度 分布を示す．ここに，b cは小数点以下を切り捨てる演算を示している．図2.2 は，頻度分布がＵ字型の左右対称な分布になっていることを示している．この 左右対称の分布特性を利用して，閾値を0.5とした閾値法で生成した2値系列 {u_t}は，

u_t=

( 0, if xt<0.5

1, else (2.3)

独立同一分布性を有することが知られている([3] pp.230-237)．この2値系列生 成法は5章で提案する「多次元乱数生成法」で用いる．

初期値敏感性 ロジスティック写像は，初期状態の微小な違いが写像を繰り返 す毎に拡大し，発散する性質を持つ．これを初期値敏感性という．例えば，計 算精度Nビットのとき，初期値x₀ = 0.0· · ·01と初期値x˜₀ = 0.0· · ·010から異 なる時系列が得られる．カオスの初期値敏感性を利用して，相対的生成速度の

第2章 整数を用いたロジスティック写像の計算

図 2.2: ロジスティック写像x_t+1 = 4x_t(1−x_t)から生成したx_tの分布．

遅い計算機でも，並列処理により，大量に異なる系列を生成することで乱数を 高速に生成できると期待されている[7]．

周期性 ロジスティック写像はカオスを生成する[1]．すなわち，周期無限長の 系列を生成できる．

しかし，計算機でロジスティック写像を計算すると，初期値敏感性を示さな い場合がある．また，生成した時系列{x_t}はいずれ周期状態に落ち入る．本研 究の目的の1つは，有限計算精度でロジスティック写像を計算するときに得ら れる系列が有する主な性質が，無限計算精度で計算し得たそれとの違いを明ら かにすることであるが，それを議論する前に，有限計算精度でロジスティック 写像を計算する際に，固定小数点を選ぶ理由を浮動小数点とその特長を比較し て述べる．

2.3. 浮動小数点と固定小数点によるロジスティック写像の計算について

2.3 浮動小数点と固定小数点によるロジスティック写 像の計算について

浮動小数点演算の特徴[21,34]

一般に，計算機の上でのカオスの計算には浮動小数点演算が用いられてきた

[7,8,12-17,19]．これらの研究では，カオスを計算して得られた系列に対し，周

期の長さや周期に落ち入る前のリーダーの長さ，そして，系列あるいはその系 列から得られた（変換やその一部の抽出など）系列が有する統計的な特性を調 査している．

浮動小数点演算の利点は限られるビット長で計算できる数値の範囲が大きい 点にある．

しかし，浮動小数点演算は，小数点の位置を計算する数値の状況に応じて変 化させているため，計算する数値に応じて計算精度は異なる．したがって，浮 動小数点を用いてカオスを計算する際に，生成される時系列は複数の計算精度 によるものとなる．

カオスを擬似乱数生成へ応用する際に，より長い周期性を持つ系列を得るに は，より高い計算精度で計算して系列を生成する必要がある．その際に，得ら れた系列が有する周期性などの性質を数値計算で調べることは，計算量的な面 で物理的にできなくなるが，把握する必要がある．浮動小数点演算で生成した 系列を観測して得られた知見は，該当特定の状況下のものであり，それらの性 質と計算精度との関係を導くことはできない．より高い計算精度で計算した系 列の有する性質への類推は困難である．

また，浮動小数点演算は計算システムによって異なる規格が存在している．そ のため，規格が異なれば，同じ入力に対して必ずしも同じ出力が得られない．さ らに，安価な産業用マイクロコントローラは浮動小数点演算をサポートしてい ない．

そして，計算精度の拡張が固定小数点演算よりも難しい．

固定小数点演算の特徴

固定小数点演算は浮動小数点演算法が開発される前では使われていたが，今 はほとんど使われていない．固定小数点演算が必要であれば，浮動小数点演算

第2章 整数を用いたロジスティック写像の計算

を用いて計算した結果を同等精度の固定小数点演算の結果に変換できるからで ある．

固定小数点演算で計算できるのは純小数だけである上，計算できる数値の範 囲が狭い．

しかし，固定小数点演算は整数型演算で実現できる．整数型の乗算器はほと んどの安価な産業用マイクロコントローラが内蔵されている．また，整数演算 は異なる計算機システムでも同じ入力に対し，同じ出力が得られる．すなわち，

汎用性が高い．

また，固定小数点演算は小数点の位置を変化しないため，常に同じ計算精度 で計算される．したがって，生成される時系列は単一の計算精度によるものと なり，単一計算精度の状態での時系列の振る舞い（初期値敏感性，周期性）を 観察できる．モンテカルロ法により，生成した時系列が有する性質と計算精度 との関係を観測することは可能になる．

さらに，計算精度の拡張が相対的容易である．

固定小数点演算の選択

浮動小数点演算方式は計算できる数値の範囲が大きいため，科学計算に多用 されてきており，ほとんどのカオスの計算もこれまで浮動小数点法を用いて計 算されている[34 p.107]．

浮動小数点演算の数値は符号部，指数部，仮数部に構成されているが，本研 究の観察では，実際にロジスティック写像を倍精度で計算するとき変化してい る（使われている）のは仮数部と指数部の一部だけである．浮動小数点の特長 は指数部を有効に使うことにより，計算できる数値の範囲を大きくした点にあ るから，ロジスティック写像の計算においては，浮動小数点の利点は有効に使 われていないことになる．

実際，3章では同じ64ビットの幅を使う固定小数点演算の場合，計算される ロジスティック写像の時系列の周期長は数億であることが数値実験の結果で明 らかになった．一方，浮動小数点演算の場合は数百万～数千万ほどである（[4]

p.41）．

式(2.2)のロジスティック写像はその式の特徴から，固定小数点演算でも計算

2.3. 浮動小数点と固定小数点によるロジスティック写像の計算について 可能である．その上，汎用性が高いこと，計算精度の拡張が相対的容易であるこ と，単一計算精度の状態での時系列の振る舞いを観察できることなどから，本 研究は固定小数点によるロジスティック写像の計算が，浮動小数点演算よりも 有利であると考える．

なお，必ずしもすべてのカオス関数に固定小数点演算を用いることができる とは限らない．ロジスティック写像のように，xtが区間(0,1)の中に値をとる純 小数であり，互いに相補するし合うx_tと(1−x_t)の乗算で次のx_t+1の値が区間 (0,1)の中に値をとる場合に限られることに注意しておく．

浮動小数点倍精度を用いて，任意に初期値を選び，ロジスティック写像を計算 して時系列を生成すると，時系列が0に落ち入るケースは約16%ほどある．し かし，これは浮動小数点演算において，下位ビットに対する丸め処理は四捨五 入を用いた場合の結果である．一方，丸め処理を切り捨てにしたときでは，時 系列が0に落ち入ることがなくなることが知られている[4](pp.41-43)．

本研究において，有効桁以下の数値は特別に指定しない限り，切捨てとする．

第2章 整数を用いたロジスティック写像の計算

2.4 整数ロジスティック写像

2.4.1 背景

ディジタル計算機を用いて，有限桁の精度でロジスティック写像を計算する方 法は，カオスが研究された当初からなされてきたが，整数ロジスティック写像と して明確な定義が与えられたのは，著者の知る限りでは，文献[18]が最初であ る．この研究では，有限桁の精度で得られた系列に対する調査結果が紹介され ている．まず，得られた整数系列に対し，整数値の特定の位置にある１ビット を抽出して，新たな2値系列を形成し，その2値系列のパワースペクトルにつ いて，また，計算精度9∼16ビットにおいて，得られた系列が有する周期長の 平均，周期に落ち入る前の長さ（リーダー）の平均，とその合計について，調 べられた．

しかし，この研究で得られた周期長やリーダー長の平均は周期長に関する頻 度分布を考慮していない．任意に初期値を選ぶ場合に，頻度分布の高い周期に 落ち入る系列になる可能性が高いため，仮に短い周期長の頻度分布が高い場合，

周期長の短い系列が生成される可能性が高くなる．

また，これまでの研究では，有限計算精度でカオスを計算するときに現れる初 期値敏感性を示さない初期値領域についての議論は，ほとんどなされていない．

2.4.2 ^定義

ここで，本論文で用いる記号ならびに用語を整理しておこう．

定義 2.1. (整数ロジスティック写像)[18] 整数ロジスティック写像とは

`_N :{0,1, . . . ,2^N −1}→{0,1, . . . ,2^N −1};

`_N(X) = b4X(2^N −X)2^−Nc，0≤X <2^N, X :整数

である．ここで，実数xに対して，bxcはx を越えない最大の整数である．¤ 本論文では，整数ロジスティック写像`_N を用いて定まる差分方程式

⎧⎪

⎨

⎪⎩

X₀ = 1以上2^N −1以下の任意の整数 X_t+1 = `_N(X_t)，t≥0

(2.4)

2.4. 整数ロジスティック写像 から生成される数列{X_t}について考察する．式(2.4)におけるX_t, t ≥ 0は 0 ≤ X_t < 2^N を満たす．式(2.4)で求まる数列{X_t}のことを整数ロジスティッ ク写像と呼ぶ場合がある．

ここで，式(2.2)におけるx_t, x_t+1 (t ≥0)に対し，仮に X_t =b2^Nx_tc, X_t+1 =b2^Nx_t+1c

とおいても，必ずしも式(2.4)は成立しないことに注意しておく．例えば，式 (2.2)を用いて，8ビットの初期値x₀ = 0.01（ここに，x_tの小数点以下は16進 表示である）に対する計算結果{x_t}に対し，b2⁸x_tcで得られた整数の系列は

01→03 →0F →3A→B5 →D3→93→FA →. . .

となる．一方，N = 8で式(2.4)を用いて，X₀ = 01（ここに，X_tは16進表示 である）に対する計算結果は

01→03 →0B →2A→8C →FD→0B→2A →. . .

となる．式(2.4)が成立する一つの十分条件は，x_tは小数点以下N 桁の2進小 数に等しいことである．実際，x_tは小数点以下無限桁が存在している．このx_t とX_tの間に存在するN + 1桁以降の微小の差がたちまち拡散され，大きな違 いになる．

以上から，式(2.2)を無限計算精度で計算して，得られた系列{x_t}に対し，

b2^Nx_tcで得られた整数の系列は，式(2.4)を計算して得られた{X_t}の系列とは 別のものとなっている．したがって，本来の{x_t}が有していた周期性や初期値 敏感性が整数ロジスティック写像によって{X_t}に整数化したことにより，どの ように変化するのかを調べることは，工学上，重要な意味を持っている．

以下では，数列X₀, X₁,· · · を整数ロジスティック写像の軌道，より正確には順 計算軌道と呼び，(X_t)と記す．

2.4.3 整数ロジスティック写像

整数ロジスティック写像の初期値敏感性

整数ロジスティック写像も，初期状態の微小な違いが写像を繰り返す毎に拡 大し，発散する性質を持つ．しかし，整数ロジスティック写像を計算するとき，

第2章 整数を用いたロジスティック写像の計算

初期値X0とX˜0が異なれば，必ず異なる時系列を生成できるとは限らない．区 間[3·2^N−3,5·2^N−3]において，異なるX₀とX˜₀をそれぞれ初期値とし，ロジス ティック写像を施すと出力は同一の系列になることがある．例えば，計算精度 32ビットのときに，初期値X₀をそれぞれ

　　　　　　7054C34C, 7054C34D, 7054C34E にして，式(2.4)を一回計算して得られたX₁は，同じ値の 　　　　　　　 FC29F163

である（X_tは16進表示）．3章で，このような初期値敏感性が示さない区間に ついて詳しく述べる．この区間の存在は乱数生成を考える上で重要になる．

整数ロジスティック写像の周期性

整数ロジスティック写像を繰返し計算していくと，生成した時系列(Xt)はいず れ周期状態に落ち入る．すなわち，任意の時点tにある値X_tに対し，X_t+S =X_t が成立するとき，軌道(X_t, X_t+1,· · · , X_t+S−1)をループと呼び，Sを周期長と呼 ぶ．しかし，任意の初期値X₀から整数ロジスティック写像を計算して，X_t=X₀ となるような状態を調べても，周期を検出できると限らない．一般に整数ロジ スティック写像を計算して時系列(X_t)を生成すると，図2.3に示すように，生

図 2.3: ループとリーダー

成されたX_tの系列は初期値X₀から始まり，リーダーと呼ばれる過渡状態[18]

を経てから周期状態に至る．偶然初期値を周期内の値にしたときだけリーダー 長`は0となるが，その可能性は極めて低い．周期性についての議論は乱数生 成法においては避けて通れない．整数ロジスティック写像の周期性については 3章において詳しく論じる．

2.5. まとめ

2.5 ^まとめ

同じビット幅を使う固定小数点演算の場合，計算される時系列の周期長は固 定小数点の方がより長いことが数値実験の結果で明らかになったことや汎用性 が高いなどを理由に，ロジスティック写像の計算に，浮動小数点演算より固定 小数点演算を選んだ．

整数によるロジスティック写像の計算は，任意の計算精度でのロジスティック 写像の計算を整数の加算，乗算，ビットの論理演算だけで実現できる．そのた め整数の加算，乗算，ビットの論理演算ができるシステムであれば，ソフトウェ ア上でも，ハードウェア上でも，同じ計算結果が得られる．

そのため，これまで計算速度の制限で実現できなかった周期性や統計的特性 などの観測が可能になり，ロジスティック写像に対する解析可能な範囲をより 広げた．ロジスティック写像の計算に，汎用性と拡張性を高め，単一計算精度 で計算した時系列の性質を観測でき，その性質と計算精度との関係を観察する ことも可能となり，更なる性質の解明が可能となる．ロジスティック写像を幅 広い分野での応用が容易となる．

次章では整数を用いた固定小数点で生成したロジスティック写像の時系列に おいて，初期値が写される先が同じ値になる場合，不動点に落ち入る系列の存 在を調べる方法，周期性などについて考察する．

第 3 ^{章 発散，収束，周期性}

概要 整数ロジスティック写像では，初期値の選び方によっては，写 される先が同じ値になる場合がある．これらの初期値の集まりを本 論文ではホール（Hall）と呼ぶ．一つのホールに含まれる初期値同 士は，明らかに初期値敏感性を示さない．ホールの存在を明らかに することは，本論文の最大の目的である擬似乱数生成ならびに，そ れを用いたインデックス法の設計に密接に関わる．

　一般のロジスティック写像の場合，初期値が不動点以外の値であっ ても，有限回の繰り返しで不動点に落ち入ることがある．ところが，

整数ロジスティック写像の場合は，この性質は自明ではない．つま り，どのような初期値の場合に，有限回の繰り返しで不動点に落ち 入るかを求めるためには，与えられた演算精度の下で，数値計算を 行う以外に手立てがない．

　そこで，本章では，整数ロジスティック写像を繰り返し計算する 過程で，不動点に落ち入ることを回避するために，不動点を含む任 意の値に落ち入る系列の存在を調べる方法を提案する．

　任意の初期値から始め，整数ロジスティック写像を繰り返し施す ことによって生成できる非周期状態の擬似乱数の長さは，生成され た数列のリーダー長とループの長さによって定まる．本章では，数 値計算により，整数ロジスティック写像が生成できる平均的な非周 期状態長と計算精度N との近似的な関係を与える．

3.1. はじめに

3.1 ^はじめに

擬似乱数生成への応用としてカオスに期待が寄せられるのは，カオスが初期 値敏感性を有するからである．しかし，整数ロジスティック写像は，初期値に よっては，初期値敏感性が示さない場合がある．すなわち，異なる初期値から 同じ系列が生成される．これらの初期値の集まりを本論文ではホール（Hall）と 呼ぶ．ホールに含まれない値を初期値として選ぶことは擬似乱数生成において 重要である．2節では整数ロジスティック写像におけるホールの大きさと計算精 度N の関係などについて議論する．

整数ロジスティック写像は，不動点以外の値を初期値にして擬似乱数を生成 するとき，一旦不動点に落ち入れば，その後何度整数ロジスティック写像を施し ても，得られた数列は全て同じ値をとる．すなわち，乱数列ではなくなる．こ のような状況にならないことは重要である．ロジスティック写像は可逆ではな いが，逆対応が存在している．3節では整数ロジスティック写像の発散とその逆 対応の収束を利用して，整数ロジスティック写像を反復繰り返し行った場合に，

不動点に入る時系列に関する調べ方とその例を示す．これを用いて，不動点以 外の初期値から不動点に落ち入ることを避けることが可能となる．

線形合同法や線形フィードバックシフトレジスタに代表される乱数生成法は 最大周期系列を利用するため，周期性については周期長のみの議論となるが，

ロジスティック写像の場合には複数の異なる周期長のループが存在し[4](p.41)， 周期状態に入る前のリーダーと呼ばれる過渡状態の系列が存在している．その ため，リーダー長`と周期長Sをあわせて議論する必要がある．これまで，整 数ロジスティック写像において，計算精度9∼16ビットのときの周期長とリー ダー長の平均値が示されたが[18]，異なる複数の周期長の頻度分布については 考慮されていない．また，特定のループと初期値との間の関係についても明ら かにされていない．4節では，数値計算の結果により，これらを考察し，異なる 複数の周期長の頻度分布を考慮した，整数ロジスティック写像における近似的 な非周期状態長と計算精度Nとの関係を与える．これは4，5章における乱数 生成器の設計時に計算精度N を決める要件の1つとなる．

本章は以下のようになる．2節は初期値敏感性が示さない場合について，3節 は整数ロジスティック写像の不動点に入る時系列に関する調べ方について，そ して4節は整数ロジスティック写像における計算精度Nと非周期状態長の近似

第3章 発散，収束，周期性

的な関係について考察し，5節は結論を述べる．

3.2. 発散

3.2 ^発散

カオスを擬似乱数の生成に応用する場合，用いるカオス関数が初期値敏感性 を有することは重要である．しかし，整数ロジスティック写像の場合，初期値 の選び方によっては，初期値敏感性が示さない，すなわち，発散しない場合が ある．整数ロジスティック写像を擬似乱数生成へ応用する際に，写される先が 同じ値になる状況を避ける必要がある．

3.2.1 ^目的

整数ロジスティック写像を低い計算精度で計算すると，初期値敏感性が示さ ない場合を観測することは容易であるが，任意に与えられた計算精度の下で，

その観測結果から初期値敏感性が示さない範囲や位置を確定することは難しい．

また，従来の浮動小数点によるロジスティック写像の計算では計算精度が計算 する数値によって変化するため，それの計算精度との関係を調査することはで きない．これまで，整数ロジスティック写像に関する初期値敏感性が示さない 範囲や位置など，計算精度との関係についての報告は見られていない．

本節は，整数ロジスティック写像において，初期値敏感性が示さない範囲と 位置を求め，さらに，それらの計算精度の影響について明らかにする．このこ とは，4，5章の乱数生成法を応用する乱数生成システムの設計時に，初期値の 取る範囲や計算精度の決定に根拠を与える．

3.2.2 準備

以下では，任意の正整数N に対し，

Z^N ={0,1, . . . ,2^N −1} とおく．

定義 3.1. 任意のX, Y ∈Z^N に対し，関係∼とは

`<sub>N</sub>(X) =`_N(Y)

となる場合で，その場合に限る．このとき，X ∼Y と記す．

第3章 発散，収束，周期性

この関係∼において，X, Y ∈Z^N に対し，

X ∼X（反射律）

X ∼Y ⇒Y ∼X（対称律）

が成立つことは容易に分かる．さらに，

X ∼Y, Y ∼Z ⇒ X ∼Z（推移律）

も成立するので，関係∼はZ^N の同値関係である．また，X, Y ∈ Z^N に対し，

`<sub>N</sub>(X)6=`_N(Y)のとき，X 6∼Y と記す．　　　　　　 ¤ 計算精度N = 8のときの整数ロジスティック写像の状態X_tの推移を図3.1(p.31) に示す．楕円で囲んだ数値（16進表示）は，整数ロジスティック写像の入力に すると同じ出力を得る．

定義 3.2. 任意のA∈Z^N−1に対し

S^A={X∈Z^N | A∼X}

とおく．　　　　　　 ¤ 集合S^AはZ^Nの同値類である．同値類S^A∩Z^N−1が少なくとも2個以上の元 を含むとき，本論文ではS^A∩Z^N−1をホール(Hall)と呼び，H^A =S^A∩Z^N−1

とおく．また，定義2.1から，X ∼2^N −Xが成立する．

１つのホールに含まれるX1, X2は初期値敏感性を示さないので，ホールは初 期値敏感性を示さない初期値を調べる上で，重要な概念となる．

ホールについては次の命題が成立する．

命題 3.1. もし，任意のA∈Z^N−1, X₁, X₂ ∈Z^N−1に対し，

X₁, X₂ ∈H^A かつX₁ < X₂ ならば，

任意のX₁ < X₃ < X₂を満たす，X₃ ∈Z^N−1に対し，

X₃ ∈H^A

3.2. 発散 である．

証明　まず，

δ_k = 4X_k(2^N −X_k)2^−N −`(X<sub>k</sub>) (k = 1,2,3)とおく．すると，`_Nの定義2.1から

0≤δ₁,δ₂,δ₃ <1 である．さらに，

`N(X3)−`N(X2) = b4X3(2^N −X3)2^−Nc−b4X2(2^N −X2)2^−Nc

= 4X₃−4X₃²/2^N −δ₃−4X₂+ 4X₂²/2^N +δ₂

= 4(X₃−X₂)(1−(X₃+X₂)/2^N) + (δ₂−δ₃)

ところで，仮定より，X₃−X₂ <0，また，1−(X₃+X₂)/2^N >0，−1<δ₂−δ₃ <1 なので，

`<sub>N</sub>(X<sub>3</sub>)−`_N(X₂)<1 (3.1) が成り立つ．同様に，

`<sub>N</sub>(X<sub>3</sub>)−`_N(X₁) = b4X₃(2^N −X₃)2^−Nc−b4X₁(2^N −X₁)2^−Nc

= 4(X3−X1)(1−(X3+X1)/2^N) + (δ1−δ3)

仮定より，X₃−X₁ >0，また，1−(X₃+X₁)/2^N > 0，−1< δ₃ −δ₁ <1 な ので，

`N(X3)−`N(X1)>−1 (3.2) さらに，`N(X1) = `N(X2)より，`N(X3) = `N(X1) = `N(X2) が成り立ち，題 意を得る．　　　　　　　 ¤ 定義 3.3. 　もし，Xと∆≥1が，

0≤X <2^N−1, 0≤X+∆<2^N−1 を満たすならば，∆`_Nを

∆`<sub>N</sub> =`_N(X+∆)−`_N(X)

で定義する．　　　　　　　 ¤