前 7 - 21 p ｜ 
もくじ i ｜ 次 7 - 23 n 
オイラーの規準の続き。
x(p-1)/2
が≡+1または≡-1であるかに応じて、xは法pでの平方数または非平方数だ。
ここで、xは整数、pは素数で、xはpの倍数でないと仮定している。
ここで、(x/p)という略記法を考える。
この(x/p)というのは、もしxが法pの平方数なら +1 という値を持ち、
さもなければ -1 という値を持つ、と定義する。これをルジェンドル記号という。つまり、いちいち「何たらを法として平方数（平方剰余）である」とか「平方数でない（平方非剰余）」とか言葉で書くと長ったらしいので、例えば、
「3は9973を法とする平方剰余だ」
ということを、 (3/9973) = 1 と略記するのである。すると、オイラーの規準は、次のように簡潔に記すことができる。
x(p-1)/2 ≡ (x/p) …… (*)
ルジェンドルの記号を使うと、単に記述が簡単になるだけでなく、次のような非常にべんりな計算が可能になる。
x = ab のとき (x/p) = (a/p)(b/p)
（x, a, bは整数。）
この計算方法は分数の計算とよく似ているので、ルジェンドル記号の形は見た目としても分かりやすいはずだ。 このような計算が可能になるわけは、原始根βを考えて、 x, a, b の離散対数をとれば明らかだ。 オイラーの規準で調べたように、平方剰余であるということは離散対数が偶数であること、 平方非剰余であるということは離散対数が奇数であることなのだから、例えば、aがβの奇数乗、bがβの偶数乗だとすると、 x = ab はβの(奇数乗)+(偶数乗)=(奇数乗)になって平方非剰余、したがってルジェンドル記号の値は -1 となる。 奇数、偶数のどういう組み合わせについてもこのことは言えるし、xが3つ以上の整数の積に分解された場合も同様になる。
次のような戦略を考える。
p が素数であれば、必ずオイラーの規準 (*) が成り立つ。 すなわち、ルジェンドル記号の値（それはxが平方数かどうかを表す）は、 x(p-1)/2 によって計算できる。
もし仮に、x(p-1)/2 の計算をしないで、何か別の方法でルジェンドル記号の値が分かったとする。 x(p-1)/2 のほうは、それはそれで別に計算するとする。 こうして求めたふたつの値は、オイラーの規準によって、p が素数であるという仮定のもとで、必ず一致する。
そこで発想を逆転させて、pの素性が分からない状態で (*) の両辺を計算してみたとする。 もし両辺を別々に計算した答が一致しなかったなら、p は素数ではない。 なぜなら、もし素数なら両辺が等しくなることがオイラーの規準によって保証されているからだ。 つまり、素数性判定に使える方法が得られる。
とは言っても、ルジェンドル記号それ自体は、「分母」 p が素数の場合にのみ定義されている。 しかし、平方数であるかないか？の判定それ自体は無視して、純粋に素数性判定にのみ使うのであれば、 次のようにルジェンドルの記号の拡張版を考えることができる。
まず「分子」の x はそのままとして、
「分母」y を素数かもしれないけれど素数でないかもしれない奇数とする（素数性を判定したいのだから、
テストしたい数が偶数だったら、こんなことをするまでもない）。
y の素因数分解を
y =
p1 e1
p2 e2
p3 e3
…
とするとき、拡張版ルジェンドル記号 (x/p) を、
(x/y) =
(x/p1) e1
(x/p2) e2
(x/p3) e3
…
と定義する。右辺の各因子は、すでに定義したふつうのルジェンドル記号だ。例えば、y = 45 = 32×5 に対して
(10/45) = (10/3)2 × (10/5)
左辺の「拡張版ルジェンドル記号」をヤコビ記号という。
もし y が素数なら、y=p1 であって、次のようにヤコビ記号はルジェンドル記号と同じ意味になる。
(x/y) = (x/p1)
具体例はすぐ下。
ヤコビ記号を定義に従って計算するには「分子」y の素因数分解が必要だ。 我々は y が素数かどうか知りたいのだから、もし y の素因数分解が分かっているのなら、 そもそも素数判定など必要ない。 ところが、実際には y を素因数分解することなく、効率的にヤコビ記号の値だけを求める方法があるので、 話が変わってくる。以下にそのアルゴリズムを示す。
ヤコビ記号 (x/y) とひっくり返した (y/x) は、 常に絶対値が等しい。そして、x, y の両方ともが ≡3 (mod 4) のときには、ひっくり返すと符号が変わる。 それ以外の場合は符号も変わらない。これは平方剰余の相互法則そのものだ。
(5/17) = (17/5) 5も17も≡3 (mod 4)でないから、単にひっくり返して良い
(11/17) = (17/11) 11は≡3だが、17は≡3でないから、単にひっくり返して良い
(11/23) = - (23/11) 11も23も≡3なので、ひっくり返すと符号が変わる
例えば、(101/3) は (2/3) に等しい。101≡2 (mod 3)だからだ。
上記の1と2を組み合わせると、巨大な数のテストが一気に簡単になる。例えば、(5/9957) = (9957/5) とひっくり返して（このとき5は≡3 (mod 4) でないから符号は変わらない）、規則2で簡約すれば = (2/5) となる。ヤコビ記号 (5/9957) をまともに計算するのは面倒だが、このように、いとも簡単な変形で小さなルジェンドル記号 (2/5) に帰着させることができる。
上記のようにしてヤコビ記号を簡約していくと、最終的には「ある法に対して2は平方数かどうか」という問題に帰着する。 つまりルジェンドル記号 (2/y) を求めたい。結論から言うと、y≡1またはy≡7 (mod 8) なら (2/y) = 1 （つまり x2 = 2 (mod y) に解がある）、しからざれば (2/y) = -1 （つまり x2 = 2 (mod y) に解がない）。
17 ≡ 1 (mod 8) だから、x2 = 2 (mod 17) は解を持つ。実際 62 = 36 ≡ 2 (mod 17)
5 は mod 8 で ≡1 でも ≡7 でもないから、x2 = 2 (mod 5) は解を持たない。 実際 02=0, 12=1, 22=4, 32=9≡4, 42=16≡1 のいずれも≡2とならない。
以上でソロベイ・ストラッセンの素数性判定について述べる準備ができた。 なお、引用した定理の証明は難しくないが、長くなるのでここでは省く。
いま、素数であるかどうか知りたい大きな数 N があるとする。
任意に選んだ小さな整数 b について、
ヤコビ記号 (b/N) ……①
を計算する。
さらに、オイラーの規準の式
b(N-1)/2 (mod N)……②
を計算する。
もし、N が素数なら、①はルジェンドル記号そのもので、オイラーの規準により（Nを法として）当然に②と一致する。
逆に、①と②が一致しない場合には、最初に述べたようにNは素数ではあり得ない。
つまり上記ソロベイ・ストラッセン・テストに合格できないNは絶対に素数ではない。
このテストに合格できる数は、たぶん素数である。
しかし、フェルマーのテストやミラーのテストと同様に、このテストでも、たまに素数でないのに合格してしまう擬素数がある。
ソロベイ・ストラッセン・テストをあざむく擬素数をオイラー擬素数という。
オイラー擬素数はフェルマー擬素数よりはまれだが、強擬素数よりは多い。
したがって、ソロベイ・ストラッセン・テストはフェルマーテストよりは強力だが、ミラーテストに比べると少し甘い。
このテストの実装や、オイラー擬素数そのものについての興味は次回以降にまわして、ここでは小さな数で実際にソロベイ・ストラッセンの判定法を実行してみよう。
概念の説明のために小さな数を用いる。実際にはこんな小さな数は試行除算であっさり判定できる。
仮に底を5として、(5/9923) を考える。ひっくり返して (9923/5) 、簡約して (3/5)、ひっくり返して (5/3)、簡約して (2/3)、ここで2の平方根に関する規則を思い出すと、3は8を法として≡1でも≡7でもないから、結局 (5/9923) = -1
これは 5(9923-1)/2 = 54961 ≡ -1 (mod 9923) と一致するから、9923はテストに合格する。実際9923は素数。
これも底5で考えると、(5/9917) = (9917/5) = (2/5) = -1
これは 5(9917-1)/2 ≡ 9216 (mod 9917) と全然一致しないから、9917は確実に合成数。
