Solovey – Strassenテスト
ロバート・ナイチンゲールと
フォルカー・ストラッセンは、ヤコビ記号を使用する数を単純化するために確率的テストアルゴリズムを開発しました。 数値を複合またはおそらく素数として定義します。 Carmichaelの数値を複合として認識します。
そのため、最初に必要な概念を紹介する必要があります。
二次控除 。 pが素数で0 <a <pの場合、xの値が次のように存在する場合、aはpを法とする2次剰余です。
x2 = a（mod p）。
aがnを法とする二次剰余であるためには、nのすべての素因数を法とする二次剰余でなければなりません。 たとえば、n = 7の場合、2次剰余は1、2、および4です。
12 = 1 = 1 mod 7、
22 = 4 = 4 mod 7、
32 = 9 = 2 mod 7
42 = 16 = 2 mod 7
52 = 25 = 1 mod 7、
62 = 36 = 1 mod 7。
逆に、次の方程式では、それらを満たすx値はありません。
x2 = 3 mod 7、
x2 = 5 mod 7
x2 = 6 mod 7。
したがって、3、5、および6という数字は、7を法とする
2次剰余です。
数pが奇数の場合、pを法とする正確に（p-1）/ 2個の二次剰余があり、pを法とする二次剰余があります。 nが2つの素数pとqの積である場合、nを法とする正確に（p-1）（q-1）/ 4つの2次剰余があります。
素数と二次剰余の関係は、ルジャンドル記号とヤコビ記号を使用して確立されます。
ルジャンドル記号 （L（a、p）と表記）は、aが整数で、pが2より大きい素数の場合に定義される関数です。ルジャンドル記号は、値0、1、および–1を取ることができます。
aがpで割り切れる場合、L（a、p）= 0
aがpを法とする2次剰余の場合、L（a、p）= 1
aがpを法とする2次非剰余の場合、L（a、p）= -1。
圧縮すると、これらの事実は次のように記述されます。
L（a、p）= a ^（（p-1）/ 2）mod p。
ルジャンドル記号計算アルゴリズム。
1. a = 1の場合、L（a、p）= 1。
2.数aが偶数の場合、L（a、p）= L（a / 2、p）*（（-1）^（（p ^ 2-1）/ 8））。
3.数aが奇数でa！= 1の場合、L（a、p）= L（p mod a、a）*（（-1）^（（a – 1）*（p – 1）/ 4 ））。
J（a、n）として示される
Jacobiシンボルは、ルジャンドルシンボルを複合モジュールに一般化したものです。 これは、すべての整数aおよび奇数の整数nに対して定義された関数です。 Jacobiシンボルは、値0、1、および–1を取ることができます。
Jacobiシンボルは次のように設定できます。
1.ヤコビ記号は、奇数nに対してのみ定義されます。
2. J（0、n）= 0。
3. nが素数の場合、aがnで割り切れる場合、J（0、n）= 0。
4. nが素数の場合、aがnを法とする2次剰余の場合、J（0、n）= 1。
5. nが素数の場合、aがnを法とする2次の非剰余の場合、J（0、n）= -1。
6. nが合成数の場合、J（a、n）= J（a、p1）* ... * J（a、pm）。ここで、p1、...、pmはnの素因数分解です。
ヤコビ記号を計算するためのアルゴリズム。
1. J（1、n）= 1。
2. J（a * b、n）= J（a、n）* J（b、n）。
3.（n ^ 2-1）/ 8が偶数の場合、J（2、n）= 1、それ以外の場合は–1。
4. J（a、n）= J（（a mod m）、n）。
5. J（a、b1 * b2）= J（a、b1）J（a、b2）。
6. gcd（a、b）= 1であり、さらに、数字aとbが奇数の場合、
6.1。 J（a、b）= J（b、a）if（a-1）*（b-1）/ 4は偶数です。
6.2。 J（a、b）= –J（b、a）if（a-1）*（b-1）/ 4が奇数の場合。
nが素数の場合、ヤコビ記号はルジャンドル記号と同等です。
ヤコビ記号を使用して、数値aがnを法とする2次剰余であるかどうかを確認することはできません（数値nが素数の場合を除く）。 J（a、n）= 1で、nが合成数である場合、数aは2次剰余であるとは限りません。
J（7、143）= J（7、11）* J（7、13）=（–1）*（-1）= 1
ただし、x27（mod 143）のような整数xはありません。
Solovey – Strassenアルゴリズム
1. p未満の乱数を選択します。
2. gcd（a、p）！= 1の場合、数値pは合成され、テストを続行できます。
3. j = a ^（（p – 1）/ 2）mod pを計算します。
4.ヤコビ記号J（a、p）を計算します。
5. j！= J（a、p）の場合、数値pは確実に素数ではありません。
6. j = J（a、p）の場合、数pが素数ではない確率は50％を超えません。
番号pは素数ではないことを明示的に示さない番号aは、証人と呼ばれます。 pが合成数の場合、乱数が目撃者である確率は少なくとも50％です。 合成数がtテストに合格する確率は1 /（2 ^ t）です。