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

ソロベイ–シュトラッセン素数判定法は、en:Robert M. Solovayとen:Volker Strassenによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではen:Baillie-PSW primality testやミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。

概要

レオンハルト・オイラーは任意の素数pと整数aに対して、

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

($\left({\tfrac {a}{p}}\right)$はルジャンドル指標)であることを証明した。 ヤコビ指標はルジャンドル指標を一般の奇数nに対する$\left({\tfrac {a}{n}}\right)$に一般化したものである。ヤコビ指標は平方剰余の相互法則のヤコビによる一般化を用いればO((log n)²)時間で計算できる。

奇数nが与えられたとき、合同式

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

がnと互いに素な様々な底aに対して成立するかどうかを考えることができる。nが素数なら、この合同式はすべてのaに対して真である。そのため、ランダムにaを取ってこの合同式をチェックすれば、成り立たないaが存在した時にnが素数でないことが言える(ただし素因数分解は分からない)。この場合の底aをnのEuler witnessと呼ぶ。このaはnが合成数であることの証拠である。もしnが合成数で上の合同式が成立するならば、そのときの底aをnのEuler liarと呼ぶ。

任意の奇数の合成数nに対して、全ての底のうち少なくとも半分の底

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

がEuler witnessである。 これは、証拠の数がずっと少なくなり得るフェルマーテストとは対照的である。そのため、フェルマーテストにおけるカーマイケル数の存在とは対照的に、証拠がたくさん存在しないような(奇数の)合成数nは存在しない。

例

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

ランダムにaを取る(ここではa = 47 < n)。このとき、

• a^(n−1)/2 mod n  =  47¹¹⁰ mod 221  =  −1 mod 221
• $({\tfrac {a}{n}})$ mod n  =  $({\tfrac {47}{221}})$ mod 221  =  −1 mod 221.

これにより、221が素数であるか、47が221のEuler liarであることが分かる。もう一つ別のa(ここではa = 2)で試す。

• a^(n−1)/2 mod n  =  2¹¹⁰ mod 221  =  30 mod 221
• $({\tfrac {a}{n}})$ mod n  =  $({\tfrac {2}{221}})$ mod 221  =  −1 mod 221.

2は221が合成数であることを示すEuler witnessであるため、47は実はEuler liarであった。なおこの方法では221の約数(13と17)については何も分からないことに注意されたい。

アルゴリズムと実行時間

このアルゴリズムは以下の疑似コードで書ける:

入力: n : 素数かどうかチェックする数; k: テストの正確性を決めるパラメータ
出力: nが合成数の場合はcomposite、そうでなければprobably prime
以下を k 回繰り返す:
  [2,n − 1]の範囲からaをランダムに選ぶ
   x ← $\left({\tfrac {a}{n}}\right)$
   if x = 0 or $a^{(n-1)/2}\not \equiv x{\pmod {n}}$ then return composite
return probably prime

冪剰余の高速なアルゴリズムを使えば、このアルゴリズムの実行時間はO(k·log³ n)である(kは異なるaでテストをする回数)。

参考文献

• Solovay, Robert M.; Strassen, Volker (1977). “A fast Monte-Carlo test for primality”. SIAM Journal on Computing 6 (1): 84–85. doi:10.1137/0206006  See also Solovay, Robert M.; Strassen, Volker (1978). “Erratum: A fast Monte-Carlo test for primality”. SIAM Journal on Computing 7 (1): 118. doi:10.1137/0207009 
• Dietzfelbinger, Martin. “Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P"”. Lecture Notes in Computer Science. 3000. ISBN 3-540-40344-2 

外部リンク

• Solovay-Strassen Implementation of the Solovay–Strassen primality test in Maple