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