テストの正確性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/15 15:31 UTC 版)
「ソロベイ–シュトラッセン素数判定法」の記事における「テストの正確性」の解説
このアルゴリズムは誤った答えを返すことがある。入力nが実際に素数であれば、出力は常に正しく「probably prime」である。しかし、入力nが合成数である場合にも、出力が「probably prime」である場合がある。そのような整数nは擬素数と呼ばれる。 nが奇数の合成数である場合、gcd(a,n) = 1であるようなaのうち少なくとも半分はEuler witnessである。これは以下のように証明できる。{a1, a2, ..., am}をEuler liarの集合とし、aをEuler witnessとする。各i = 1,2,...,mに対して次が成り立つ: ( a ⋅ a i ) ( n − 1 ) / 2 = a ( n − 1 ) / 2 ⋅ a i ( n − 1 ) / 2 = a ( n − 1 ) / 2 ⋅ ( a i n ) ≢ ( a n ) ( a i n ) ( mod n ) {\displaystyle (a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}} ( a n ) ( a i n ) = ( a ⋅ a i n ) {\displaystyle \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right)} なので、 ( a ⋅ a i ) ( n − 1 ) / 2 ≢ ( a ⋅ a i n ) ( mod n ) . {\displaystyle (a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.} が成り立つ。 これにより、各Euler liar aiに対して、a·aiがEuler witnessになる。そのため、Euler witnessの個数はEuler liarの個数以上である。それゆえ、nが合成数ならば、gcd(a,n) = 1となるaのうち少なくとも半分はEuler witnessである。 このため、失敗の確率は最大で2−kである(ミラー-ラビン素数判定法の失敗の確率(最大4−k)と比較されたい)。 暗号の目的で使用する場合、沢山のaでテストするほど、つまり十分大きなkを選べば、テストはより正確になる。そのためこのアルゴリズムが失敗する可能性はとても低いので、実用的な暗号への応用においてはこの方法で得られた(擬似)乱数が使われる。しかし、素数を得ることが重要であるような応用においては、ECPP（英語版）やPocklingtonのような素数性を「証明」するテストを使用すべきである。
※この「テストの正確性」の解説は、「ソロベイ–シュトラッセン素数判定法」の解説の一部です。
「テストの正確性」を含む「ソロベイ–シュトラッセン素数判定法」の記事については、「ソロベイ–シュトラッセン素数判定法」の概要を参照ください。
- テストの正確性のページへのリンク
