| 講演名 | 2005-07-21 Miller-Rabinテストでの誤判定確率の実験的計測値と理論的上界値との比較 中島 俊哉, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | Miller-Rabinテストにおける誤判定確率(強probable primeが強擬素数である確率)の理論上界を, ビット長100以上300以下のランダムに生成した奇数について計測した実験値と比較した.その結果, 理論での期待値により各ビット長で16個程度強擬素数が観測されるはずの強probable primeの個数について実際には強擬素数は全く観測されなかった.この結果を統計的に解析することにより, 300ビット以下での実際の誤判定確率は95%の信頼度で現状での最小の理論上界よりも1/4以下であろうという推測値を得た. |
| 抄録(英) | We compare theoretical upper bounds of error probability of the Miller-Rabin test(probability that a strong probable prime is a strong pseudoprime) with experimental results for randomly generated odd integers of 100-300 bitlength. The number of strong probable primes we test is the theory-conjectured number in which about sixteen strong pseudoprimes would be found for each bitlength. After the experiment, no strong pseudoprimes were found. Analyzing this result by statistical inference, we estimate with 95% upper confidence limit that the real error probability for the range of tested bitlength is less than 1/4 of the minimum theoretical upper bound. |
| キーワード(和) | 素数判定 / Miller-Rabinテスト / 誤判定確率 |
| キーワード(英) | primality proving / Miller-Rabin test / error probability / IEEE P1363 |
| 資料番号 | ISEC2005-15,SITE2005-13 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2005/7/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Miller-Rabinテストでの誤判定確率の実験的計測値と理論的上界値との比較 |
| サブタイトル（和） | |
| タイトル（英） | Comparison of Error Probabilities of The Miller-Rabin Test by Experimental Measurement Value and Theoretical Upper Bound |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 素数判定 / primality proving |
| キーワード(2)（和/英） | Miller-Rabinテスト / Miller-Rabin test |
| キーワード(3)（和/英） | 誤判定確率 / error probability |
| 第 1 著者 氏名（和/英） | 中島 俊哉 / Toshiya NAKAJIMA |
| 第 1 著者 所属（和/英） | (株)富士通研究所 Fujitsu Laborartories Ltd. |
| 発表年月日 | 2005-07-21 |
| 資料番号 | ISEC2005-15,SITE2005-13 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 193 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |