1

Miller-Rabin 検定では、k個の乱数整数を使用して素数性を検定します。

CLRS、第 3 版、971 ページによると:

定理 31.38

n が奇数の合成数である場合、n の合成数の証人の数は少なくとも (n - 1)/2 です。

それでは、ランダムなテストを k 回実行する代わりに、異なる( n - 1 ) / 2 の値を使用してそれらの素数性をテストしてみませんか? 2 を除くすべての素数は奇数であり、目撃者は少なくとも ( n - 1 ) / 2 ではないため、存在する場合、目撃者を見つけることが保証されます。

4

1 に答える 1

3

実行時間は poly(log(n)) から n*poly(log(n)) になります。これは、n が log(n) よりも指数関数的に大きいため、大きな数の場合はひどい結果になります。

于 2016-06-06T14:05:50.870 に答える