確率と情報の科学

乱数生成と計算量理論

アルゴリズム的に乱数を生成する機構の背景にどんな数理があるのか,計算理論的な側面について解説する.

乱数生成と計算量理論
著者 小柴 健史
ジャンル 書籍 > 単行本 > 計算機科学
書籍 > 自然科学書
シリーズ 確率と情報の科学
刊行日 2014/11/27
ISBN 9784000069755
Cコード 3341
体裁 A5 ・ 上製 ・ カバー ・ 164頁
定価 3,300円
在庫 在庫あり
何の規則性も持たない数列である「乱数」は計算量理論・情報理論・統計学の境界領域にあり,諸分野がうまく融合して基礎理論が構成されている.コンピュータでアルゴリズム的に乱数を生成する機構の背景に,どんな数理があるのか.「真の乱数」から「擬似乱数」を生成する方法と,逆に擬似乱数から真の乱数を抽出する理論を解説する.

■著者からのメッセージ

 本書の目的は,アルゴリズム的に乱数を生成する機構の背景にある数理に関心のある読者を想定して,乱数生成に関しての計算理論的な側面について解説することにある.乱数生成は計算量理論・情報理論・統計学の境界領域にあるが, 諸分野が上手く融合して基礎理論が構成されている点を強調したい.特に,計算理論の観点から乱数生成の2つの側面,つまり,真の乱数から擬似乱数を生成する方法論と,擬似乱数から真の乱数を抽 出する理論について解説を行い,乱数生成の計算理論的な視点を与える ことを目指している.
――「まえがき」より

■著者からのメッセージ

 本書の目的は,アルゴリズム的に乱数を生成する機構の背景にある数理に関心のある読者を想定して,乱数生成に関しての計算理論的な側面について解説することにある.乱数生成は計算量理論・情報理論・統計学の境界領域にあるが, 諸分野が上手く融合して基礎理論が構成されている点を強調したい.特に,計算理論の観点から乱数生成の2つの側面,つまり,真の乱数から擬似乱数を生成する方法論と,擬似乱数から真の乱数を抽 出する理論について解説を行い,乱数生成の計算理論的な視点を与える ことを目指している.
――「まえがき」より
まえがき
1 なぜ擬似乱数生成なのか
1.1 物理と乱数
1.2 アルゴリズムと乱数
1.3 暗号と乱数
1.4 乱数抽出
2 擬似乱数生成
2.1 線形合同法の出力系列の非乱数性
2.2 上位ビットを出力する線形合同法
2.3 その他の擬似乱数生成法と予測可能性
2.4 乱数性の統計的検定について
3 擬似乱数生成のための計算量理論
3.1 確率論の小道具
3.2 一方向性関数
3.3 擬似乱数性と次ビット予測困難性
3.4 ハードコア述語
3.5 一方向性置換と擬似乱数
3.6 ハードコア関数
3.7 一方向性関数と擬似乱数
4 計算量理論的な擬似乱数生成法の具体的構成
4.1 具体的な擬似乱数生成法
4.2 具体的な関数におけるハードコア述語証明
5 乱数抽出器
5.1 準備
5.2 諸定義
5.3 限界と可能性について
5.4 ハッシュ平滑化補題
5.5 一般の乱数抽出器
5.6 決定性乱数抽出器

参考文献
索引
小柴健史(こしば たけし)
1967年生まれ.2001年3月,東京工業大学大学院情報理工学研究科数理・計算科学専攻博士後期課程を修了,博士(理学).通信・放送機構の情報通信セキュリティ技術研究開発プロジェクト,科学技術振興機構のERATO今井量子計算機構プロジェクトに研究員として従事.2005年4月より埼玉大学工学部助教授,現在,同大学院理工学研究科准教授.統計数理研究所にて客員助教授/客員准教授(2006~2009年),パリ大学LRI/LIAFAにて訪問研究員(2010~2011年).小柴健史(こしば たけし)
1967年生まれ.2001年3月,東京工業大学大学院情報理工学研究科数理・計算科学専攻博士後期課程を修了,博士(理学).通信・放送機構の情報通信セキュリティ技術研究開発プロジェクト,科学技術振興機構のERATO今井量子計算機構プロジェクトに研究員として従事.2005年4月より埼玉大学工学部助教授,現在,同大学院理工学研究科准教授.統計数理研究所にて客員助教授/客員准教授(2006~2009年),パリ大学LRI/LIAFAにて訪問研究員(2010~2011年).
ページトップへ戻る