ソロベイ–シュトラッセン素数判定法

ソロベイ–シュトラッセン素数判定法（）は、とフォルカー・シュトラッセンによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではやミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。
概要.
レオンハルト・オイラーは任意の素数"p"と整数"a"に対して、
(formula_2は)であることを証明した。はルジャンドル指標を一般の奇数"n"に対するformula_3に一般化したものである。ヤコビ指標は平方剰余の相互法則のヤコビによる一般化を用いればO((log "n")2)時間で計算できる。
奇数"n"が与えられたとき、合同式
が"n"と互いに素な様々な底"a"に対して成立するかどうかを考えることができる。"n"が素数なら、この合同式はすべての"a"に対して真である。そのため、ランダムに"a"を取ってこの合同式をチェックすれば、成り立たない"a"が存在した時に"n"が素数でないことが言える(ただし素因数分解は分からない)。この場合の底"a"を"n"のEuler witnessと呼ぶ。この"a"は"n"が合成数であることの証拠である。もし"n"が合成数で上の合同式が成立するならば、そのときの底"a"を"n"のEuler liarと呼ぶ。
任意の奇数の合成数"n"に対して、全ての底のうち少なくとも半分の底
がEuler witnessである。これは、証拠の数がずっと少なくなり得るフェルマーテストとは対照的である。そのため、フェルマーテストにおけるカーマイケル数の存在とは対照的に、証拠がたくさん存在しないような(奇数の)合成数"n"は存在しない。
例.
"n" = 221が素数かどうかを判定したいとする。("n"−1)/2=110である。
ランダムに"a"を取る(ここでは"a" = 47 < "n")。このとき、
これにより、221が素数であるか、47が221のEuler liarであることが分かる。もう一つ別の"a"(ここでは"a" = 2)で試す。
2は221が合成数であることを示すEuler witnessであるため、47は実はEuler liarであった。なおこの方法では221の約数(13と17)については何も分からないことに注意されたい。
アルゴリズムと実行時間.
このアルゴリズムは以下の疑似コードで書ける:
 入力: "n" : 素数かどうかチェックする数; "k": テストの正確性を決めるパラメータ
 出力: "n"が合成数の場合は"composite"、そうでなければ"probably prime"
 以下を "k" 回繰り返す:
 [2,"n" − 1]の範囲から"a"をランダムに選ぶ
 "x" ← formula_10
 if "x" = 0 or formula_11 then return "composite"
 return "probably prime"
冪剰余の高速なアルゴリズムを使えば、このアルゴリズムの実行時間はO("k"·log3 "n")である("k"は異なる"a"でテストをする回数)。
テストの正確性.
このアルゴリズムは誤った答えを返すことがある。入力"n"が実際に素数であれば、出力は常に正しく「probably prime」である。しかし、入力"n"が合成数である場合にも、出力が「probably prime」である場合がある。そのような整数"n"は擬素数と呼ばれる。
"n"が奇数の合成数である場合、gcd("a","n") = 1であるような"a"のうち少なくとも半分はEuler witnessである。これは以下のように証明できる。{"a"1, "a"2, ..., "a""m"}をEuler liarの集合とし、"a"をEuler witnessとする。各"i" = 1,2...,"m"に対して次が成り立つ:
なので、
が成り立つ。
これにより、各Euler liar "a""i"に対して、"a"·"a""i"がEuler witnessになる。そのため、Euler witnessの個数はEuler liarの個数以上である。それゆえ、"n"が合成数ならば、gcd("a","n") = 1となる"a"のうち少なくとも半分はEuler witnessである。
このため、失敗の確率は最大で2−"k"である(ミラー-ラビン素数判定法の失敗の確率(最大4−"k")と比較されたい)。
暗号の目的で使用する場合、沢山の"a"でテストするほど、つまり十分大きな"k"を選べば、テストはより正確になる。そのためこのアルゴリズムが失敗する可能性はとても低いので、実用的な暗号への応用においてはこの方法で得られた(擬似)乱数が使われる。しかし、素数を得ることが重要であるような応用においては、やPocklingtonのような素数性を「証明」するテストを使用すべきである。