判定の正確度
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 15:53 UTC 版)
「ミラー–ラビン素数判定法」の記事における「判定の正確度」の解説
より多くの a で判定を行えば、正確度が高くなる。任意の奇数の合成数 n について、a の少なくとも 3/4 が合成性の証拠となることがわかっている。ミラー-ラビン素数判定法において n についての「強い嘘つき」となる数の集合は、ソロベイ–シュトラッセン素数判定法で嘘つきとなる数の集合の部分集合であり、多くの場合は真部分集合となる。つまり、ミラー-ラビン素数判定法はソロベイ–シュトラッセン素数判定法よりも強力である。n が合成数なのに素数の可能性があると判定してしまう確率は最大で 4 − k {\displaystyle 4^{-k}} である。一方、ソロベイ–シュトラッセン素数判定法では最大 2 − k {\displaystyle 2^{-k}} となる。 合成数を素数に間違ってしまう平均確率は 4 − k {\displaystyle 4^{-k}} よりずっと小さい。Damgård、Landrock、Pomeranceはこの値を正確に求めたことがある。しかし、そのような確率は素数を生成する際には利用できるが、素性の知れない数の素数判定には依存すべきでない。特に暗号では敵が素数を強擬素数にすり替える可能性を考慮しなくてはならない。従って、 4 − k {\displaystyle 4^{-k}} という確率だけを信用すべきである。
※この「判定の正確度」の解説は、「ミラー–ラビン素数判定法」の解説の一部です。
「判定の正確度」を含む「ミラー–ラビン素数判定法」の記事については、「ミラー–ラビン素数判定法」の概要を参照ください。
- 判定の正確度のページへのリンク
