| 講演名 | 2008-02-29 T-Codeを用いた乱数検定手法の構成法について(情報通信基礎サブソサイエティ合同研究会) 濱野 健二, 山本 博資, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | T-Codeを用いた新しい乱数検定手法を提案する.T-Codeは,Mark Titchenerによって1984年に提案された自己同期する可変長符号である.T-decompositionと呼ばれる変換により,系列とT-Codeとを対応させて,系列をT-prefixと呼ばれる部分系列に分解することができる.これらの部分系列は,系列に対応するT-Codeを再帰的に生成するアルゴリズムのパラメータになっている.本検定は,これらの部分系列の個数(T-complexity)に基づく.更に,系列の先頭から順にT-prefixを決定するT-decompositionの方法と,木構造を利用した効率の良いアルゴリズムを提案する.このアルゴリズムは,T-decompositionの計算時間を削減し,本検定の計算時間を実用的にしている.また,本検定の妥当性は,T-complexity,P値等の経験分布によって確かめられている. |
| 抄録(英) | We propose a new randomness test based on T-Codes. T-Codes are variable-length self-synchronization codes introduced by Mark Titchener in 1984. A given sequence is related to a T-Code set by T-decomposition, and it is decomposed into sub-sequences called T-prefixes which are a series of parameters obtained by a recursive construction algorithm of the T-Code set. In our test, the number of the sub-sequences called T-complexity is used. Furthermore, we propose a new T-decomposition, which can determine the T-prefixes from the beginning to the end of a sequence, and an efficient algorithm of the new T-decomposition by using a tree structure. Reducing the computation time of the T-decomposition, this algorithm makes our new test suitable for practical use in the sense of computational complexity. The validity of our test is also verified by the empirical distribution of T-complexity and P-value. |
| キーワード(和) | 乱数検定 / T-Code / T-decomposition / NIST SP800-22 / Lempel-Ziv圧縮検定 / 複雑度 |
| キーワード(英) | randomness test / T-Code / T-decomposition / NIST SP800-22 / Lempel-Ziv compression test / complexity |
| 資料番号 | IT2007-55,ISEC2007-152,WBS2007-86 |
| 発行日 |
| 研究会情報 | |
| 研究会 | WBS |
|---|---|
| 開催期間 | 2008/2/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Wideband System(WBS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | T-Codeを用いた乱数検定手法の構成法について(情報通信基礎サブソサイエティ合同研究会) |
| サブタイトル（和） | |
| タイトル（英） | Construction of Randomness Testing Based on T-Codes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 乱数検定 / randomness test |
| キーワード(2)（和/英） | T-Code / T-Code |
| キーワード(3)（和/英） | T-decomposition / T-decomposition |
| キーワード(4)（和/英） | NIST SP800-22 / NIST SP800-22 |
| キーワード(5)（和/英） | Lempel-Ziv圧縮検定 / Lempel-Ziv compression test |
| キーワード(6)（和/英） | 複雑度 / complexity |
| 第 1 著者 氏名（和/英） | 濱野 健二 / Kenji HAMANO |
| 第 1 著者 所属（和/英） | 東京大学大学院新領域創成科学研究科 Graduate School of Frontier Sciences, The University of Tokyo |
| 第 2 著者 氏名（和/英） | 山本 博資 / Hirosuke YAMAMOTO |
| 第 2 著者 所属（和/英） | 東京大学大学院新領域創成科学研究科 Graduate School of Frontier Sciences, The University of Tokyo |
| 発表年月日 | 2008-02-29 |
| 資料番号 | IT2007-55,ISEC2007-152,WBS2007-86 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 503 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |