アルゴリズムと実行時間
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/15 15:31 UTC 版)
「ソロベイ–シュトラッセン素数判定法」の記事における「アルゴリズムと実行時間」の解説
このアルゴリズムは以下の疑似コードで書ける: 入力: n : 素数かどうかチェックする数; k: テストの正確性を決めるパラメータ出力: nが合成数の場合はcomposite、そうでなければprobably prime以下を k 回繰り返す: [2,n − 1]の範囲からaをランダムに選ぶ x ← ( a n ) {\displaystyle \left({\tfrac {a}{n}}\right)} if x = 0 or a ( n − 1 ) / 2 ≢ x ( mod n ) {\displaystyle a^{(n-1)/2}\not \equiv x{\pmod {n}}} then return compositereturn probably prime 冪剰余の高速なアルゴリズムを使えば、このアルゴリズムの実行時間はO(k·log3 n)である(kは異なるaでテストをする回数)。
※この「アルゴリズムと実行時間」の解説は、「ソロベイ–シュトラッセン素数判定法」の解説の一部です。
「アルゴリズムと実行時間」を含む「ソロベイ–シュトラッセン素数判定法」の記事については、「ソロベイ–シュトラッセン素数判定法」の概要を参照ください。
アルゴリズムと実行時間
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 15:53 UTC 版)
「ミラー–ラビン素数判定法」の記事における「アルゴリズムと実行時間」の解説
このアルゴリズムは次のように表現される: 入力: n > 1 {\displaystyle n>1} : 素数判定対象の奇数の整数; k {\displaystyle k} : 判定の正確度を指定するパラメータ 出力: n {\displaystyle n} が合成数なら composite、さもなくば probably prime n − 1 {\displaystyle n-1} を 2 のべき乗で割って、 2 s ⋅ d {\displaystyle 2^{s}\cdot d} の形式にする。 以下を k {\displaystyle k} 回繰り返す:[ 1 , n − 1 {\displaystyle 1,n-1\ } ] の範囲から a {\displaystyle a} をランダムに選ぶ。 a d ≠ 1 mod n {\displaystyle a^{d}\neq 1\ {\bmod {\ }}n} で、かつ [ 0 , s − 1 {\displaystyle [0,s-1\ } ] の範囲の全ての r {\displaystyle r} について a 2 r d mod n ≠ − 1 {\displaystyle a^{{2^{r}}d}\ {\bmod {\ }}n\neq \ -1} なら、composite を返す。 probably prime を返す。 平方の繰り返しをべき剰余を使って実現すると、このアルゴリズムの実行時間は O(k × log3 n) となる。ここで、k は異なる a で判定を行う回数である。以上から、このアルゴリズムが多項式時間の効率のよいアルゴリズムであることがわかる。FFTベースの乗算によって実行時間を Õ(k × log2 n) まで抑えることができる。
※この「アルゴリズムと実行時間」の解説は、「ミラー–ラビン素数判定法」の解説の一部です。
「アルゴリズムと実行時間」を含む「ミラー–ラビン素数判定法」の記事については、「ミラー–ラビン素数判定法」の概要を参照ください。
- アルゴリズムと実行時間のページへのリンク
