WEKO3
アイテム
Miller-Rabin素数判定法における誤り確率の上限
http://hdl.handle.net/10748/4127
http://hdl.handle.net/10748/41274f564a36-87e5-4f48-8059-6142f21e30f3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10236-001.pdf (2.8 MB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-09-28 | |||||||
| タイトル | ||||||||
| タイトル | Miller-Rabin素数判定法における誤り確率の上限 | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||||
| 資源タイプ | thesis | |||||||
| 著者 |
後藤, 大和
× 後藤, 大和
|
|||||||
| 著者(ヨミ) |
ゴトウ, ヤマト
× ゴトウ, ヤマト |
|||||||
| 著者別名 |
Goto, Yamato
× Goto, Yamato |
|||||||
| 抄録 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | 素数は無数に存在し、今日、暗号論など様々なところで利用されている。与えられた自然数が素数であるか判定する方法の一つとして『Miller-Rabin素数判定法』という素数判定法がある。Miller-Rabin素数判定法は確率的素数判定法と呼ばれ、判定する自然数が素数であれば必ず「素数の可能性あり」と出力するが、合成数であってもある一定の確率で「素数の可能性あり」と出力してしまう。しかし、現在発表されている唯一の決定多項式時間で計算できる『AKS素数判定法』は計算量が高すぎるため、少ない計算量で済むMiller-Rabin素数判定法等の確率的素数判定法がよく利用されている。本論文では、一般的に実用できるレベルではないものの、簡単な前処理を行うことで、ある特定の場合を除きMiller-Rabin素数判定法における誤判定の確率を下げる方法を紹介する。 | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 首都大学東京, 2011-03-25, 修士（理学） | |||||||
| 書誌情報 | 発行日 2011-03-25 | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||
