ソロベイ・ストラッセン素数検定

1977 年にRobert M. SolovayとVolker Strassenによって開発されたSolovay–Strassen 素数判定法は、数が合成数か、おそらく素数かを判定する確率的素数判定法です。この判定法の背後にあるアイデアは、1967 年に MM Artjuhov によって発見されました^{[ 1 ]} (論文中の定理 E を参照)。この判定法は、Baillie–PSW 素数判定法やMiller–Rabin 素数判定法にほぼ取って代わられましたが、 RSA暗号システムの実際的な実現可能性を示すという点で歴史的に非常に重要な意味を持っています。

オイラーは^{[ 2 ]}任意の奇素数pと任意の整数aに対して、

${\displaystyle a^{(p-1)/2}\equiv \left({\frac {a}{p}}\right){\pmod {p}}}$

どこ${\displaystyle \left({\tfrac {a}{p}}\right)}$はルジャンドル記号です。ヤコビ記号はルジャンドル記号を一般化したものです。${\displaystyle \left({\tfrac {a}{n}}\right)}$ここで、nは任意の奇数です。ヤコビ記号は、ヤコビによる 二次相互法則の一般化を用いて、 O ((log n )²) の時間で計算できます。 

奇数nが与えられた場合、合同式が成り立つかどうかを考察することができる。

${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$

基底aのさまざまな値に対して、a がnと互いに素であるという条件の下で、この合同式が成り立ちます。nが素数であれば、この合同式はすべてのaに対して成り立ちます。したがって、 aの値をランダムに選択して合同式をテストすると、合同式に合わないaが見つかった時点で、nが素数ではないことがわかります (ただし、これはnの非自明な因数分解を示すものではありません)。この基底aはnのオイラー証拠と呼ばれ、 nが合成数であることの証拠となります。nが合成数であるにもかかわらず合同式が成り立つ場合、基底aはnのオイラー嘘つきと呼ばれます。

任意の奇数nに対して、すべての塩基の少なくとも半分

${\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$

オイラーの嘘つきの集合は (オイラー) 証人であり、オイラーの嘘つきの集合は、${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$例えば、${\displaystyle n=65}$オイラーの嘘つきの集合は8次であり、${\displaystyle =\{1,8,14,18,47,51,57,64\}}$、 そして${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$注文番号は48です。

これは、フェルマー素数判定法とは対照的である。フェルマー素数判定法では、証拠となる数の割合がはるかに小さくなる可能性がある。したがって、フェルマー素数判定法におけるカーマイケル数の場合とは異なり、多くの証拠となる数を持たない（奇数の）合成数nは存在しない。

n = 221が素数かどうかを判定したいとします。( n − 1)/2 = 110 と書きます。

ランダムにa (1 より大きくnより小さい)を選択します。47 です。バイナリべき乗などの効率的な方法を使用して、数値を (mod n ) でべき乗し、計算します。

• a ^{( n − 1)/2} mod n = 47 ¹¹⁰ mod 221 = − 1 mod 221
• ${\displaystyle \left({\tfrac {a}{n}}\right){\bmod {n}}=\left({\tfrac {47}{221}}\right){\bmod {2}}21=-1{\bmod {2}}21}$

これは、221が素数であるか、47が221に対するオイラーの嘘であることを意味します。別のランダムなaを試してみましょう。今回はa = 2を選択します。

• a ^{( n − 1)/2} mod n = 2 ¹¹⁰ mod 221 = 30 mod 221
• ${\displaystyle \left({\tfrac {a}{n}}\right){\bmod {n}}=\left({\tfrac {2}{221}}\right){\bmod {2}}21=-1{\bmod {2}}21}$。

したがって、2は221が合成数であることのオイラー的証拠であり、47は実際にはオイラー的嘘つきであった。ただし、これは221の素因数（実際には13と17）については何も教えてくれないことに注意されたい。

このアルゴリズムは、擬似コードで以下のように記述できます。

入力: n、素数判定を行う値 k 、判定の精度を決定するパラメータ 出力 : nが合成数の場合はcomposite、それ以外の場合はおそらく素数k回繰り返す：[2, n − 1] の範囲からランダムに1 を 選択します。${\displaystyle x\gets \left({\tfrac {a}{n}}\right)}$x  =  0または​${\displaystyle a^{(n-1)/2}\not \equiv x{\pmod {n}}}$合成数を返したら、おそらく素数を返した

モジュラべき乗の高速アルゴリズムを使用すると、このアルゴリズムの実行時間は O( k ·log ³ n ) になります。ここで、kはテストされるaの異なる値の数です。

アルゴリズムが誤った答えを返す可能性はあります。入力「n」が実際に素数であれば、出力は常に正しく「おそらく素数」となります。

nが奇数かつ合成数の場合、 gcd( a , n ) = 1となるすべてのaの少なくとも半分はオイラーの証人である。これを次のように証明できる。{a1, a2, ..., am}をオイラーの嘘つきとし、_aをオイラーの証人とする。すると、i = 1, ₂ , ..., _mに対して、次のようになる。    

${\displaystyle (a\cdot a_{i})^{(n-1)/2}=a^{(n-1)/2}\cdot a_{i}^{(n-1)/2}=a^{(n-1)/2}\cdot \left({\frac {a_{i}}{n}}\right)\not \equiv \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right){\pmod {n}}.}$

なぜなら、以下のことが成り立つからである。

${\displaystyle \left({\frac {a}{n}}\right)\left({\frac {a_{i}}{n}}\right)=\left({\frac {a\cdot a_{i}}{n}}\right),}$

今私たちは知っている

${\displaystyle (a\cdot a_{i})^{(n-1)/2}\not \equiv \left({\frac {a\cdot a_{i}}{n}}\right){\pmod {n}}.}$

これにより、各a _{i は}、オイラーの証拠でもある数a · a _iを与えることがわかります。したがって、各オイラーの嘘つきはオイラーの証拠を与え、オイラーの証拠の数はオイラーの嘘つきの数以上になります。したがって、n が合成数の場合、 gcd( a , n ) = 1 を満たすすべてのaの少なくとも半分はオイラーの証拠です。  

したがって、失敗の確率は最大で 2 ^{− k}です (ミラー-ラビン素数判定の失敗の確率は最大で 4 ^{− k}です)。

暗号化の目的においては、テストする基底の数が多いほど、つまりkの値が十分に大きいほど、テストの精度は向上します。したがって、この方法でアルゴリズムが失敗する可能性は非常に小さいため、（擬似）素数は暗号化アプリケーションで実際に使用されますが、素数を持つことが重要なアプリケーションでは、素数性を証明するECPPやポックリントン素数判定法^{[ 3 ]}のようなテストを使用する必要があります。

Solovay–Strassenテストの1ラウンドのエラー確率の上限1/2は任意の入力nに対して成り立つが、上限が（近似的に）達成されるnの値は極めてまれである。平均的には、アルゴリズムのエラー確率は大幅に小さく、1/2未満である。

${\displaystyle 2^{-k}\exp \left(-(1+o(1)){\frac {\log x\,\log \log \log x}{\log \log x}}\right)}$

k回のテストに対して、一様乱数n ≤ xに適用される。^{[ 4 ] [ 5 ]}同じ境界は、k回のテストで素数と宣言された乱数n ≤ xに対して、 nが合成数である条件付き確率は何かという関連問題にも適用される。

Solovay – Strassen アルゴリズムは、決定問題COMPOSITE が複雑性クラスRPに属することを示している。^{[ 6 ]}

• Solovay, Robert M.; Strassen, Volker (1977). "素数判定のための高速モンテカルロテスト". SIAM Journal on Computing . 6 (1): 84–85 . doi : 10.1137/0206006 .Solovay, Robert M.、Strassen, Volker (1978)「正誤表：素数判定のための高速モンテカルロテスト」SIAM Journal on Computing 7 ( 1): 118. doi : 10.1137/0207009も参照。
• ディーツフェルビンガー、マーティン（2004年6月29日）「多項式時間での素数判定、ランダム化アルゴリズムから「PRIMES Is in P」まで」「.コンピュータサイエンス講義ノート. 第 3000巻. Springer. ISBN 978-3-540-40344-9。

• Solovay-Strassen法によるMapleでの素数判定の実装