
_START_ARTICLE_
ソロベイ–シュトラッセン素数判定法
_START_PARAGRAPH_
ソロベイ–シュトラッセン素数判定法（英: Solovay–Strassen primality test）は、Robert M. Solovayとフォルカー・シュトラッセンによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではBaillie–PSW primality testやミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。
_START_SECTION_
アルゴリズムと実行時間
_START_PARAGRAPH_
このアルゴリズムは以下の疑似コードで書ける:_NEWLINE_入力: n : 素数かどうかチェックする数; k: テストの正確性を決めるパラメータ出力: nが合成数の場合はcomposite、そうでなければprobably prime_NEWLINE_以下を k 回繰り返す:_NEWLINE_  [2,n − 1]の範囲からaをランダムに選ぶ   x ← _NEWLINE_   if x = 0 or  then return composite_NEWLINE_return probably prime_NEWLINE_冪剰余の高速なアルゴリズムを使えば、このアルゴリズムの実行時間はO(k·log³ n)である(kは異なるaでテストをする回数)。