| 講演名 | 2002/11/8 Miller-Rabinの確率的素数判定法の試行回数に関する予想 今村 恭己, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Miller-Rabinの確率的素数判定法(MR法)は、公開鍵暗号で必要となる10進で300桁程度の大きな素数を見付けるための素数判定法として良く用いられる。MR法では、大きな奇数nが素数であるか合成数であるかの判定を、ランダムに選んだb(1 |
| 抄録(英) | The Miller-Rabin probabilistic primality test is useful for finding large primes necessary for public key cryptography. For an odd composite n, an integer b in (1, n-1) is called a witness of n if b is coprime to n and n is a strong pseudoprime to the base b. It is known that at least three fourths of integers in (1, n-1) are witnesses of n. We will present a following conjecture on the upper bound of the minimum witness of n: Let k be the least integer greater than or equal to log n/log 4. Let PRIME(k) be the set of the smallest k primes. If n is composite, then there exists a witness of n in the set PRIME(k). |
| キーワード(和) | Miller-Rabinの確率的素数判定法 / 合成数nのwitness / 最小のwitnessの上界に関する予想 |
| キーワード(英) | Miller-Rabin probabilistic primality test / witness of an odd composite / a conjecture on the upper bound of the minimum witness |
| 資料番号 | ISEC2002-88 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2002/11/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Miller-Rabinの確率的素数判定法の試行回数に関する予想 |
| サブタイトル（和） | |
| タイトル（英） | A Conjecture on the Trial Number of the Miller-Rabin Probabilistic Primality Test |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Miller-Rabinの確率的素数判定法 / Miller-Rabin probabilistic primality test |
| キーワード(2)（和/英） | 合成数nのwitness / witness of an odd composite |
| キーワード(3)（和/英） | 最小のwitnessの上界に関する予想 / a conjecture on the upper bound of the minimum witness |
| 第 1 著者 氏名（和/英） | 今村 恭己 / Kyoki IMAMURA |
| 第 1 著者 所属（和/英） | 九州工業大学情報工学部 Faculty of Computer Science & Systems Engineering, Kyushu Institute of Technology |
| 発表年月日 | 2002/11/8 |
| 資料番号 | ISEC2002-88 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 437 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |