オイラー・ヤコビ擬素数

整数論では、奇数 nは、 aとnが互いに素であるとき、 aを基底とするオイラー・ヤコビ確率素数（または、より一般的にはオイラー確率素数）と呼ばれ、

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

ここで、はヤコビ記号です。ヤコビ記号は、aとnが互いに素でない場合 0 と評価されるため、このテストは次のように表現することもできます。 ${\displaystyle \left({\frac {a}{n}}\right)}$

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

n が上記の合同性を満たす奇数の合成整数である場合、 n はa を基底とするオイラー・ヤコビ擬素数（または、より一般的にはオイラー擬素数）と呼ばれます。

aがnの倍数でない限り(通常 2 ≤ a < n )、 aとn が互いに素でない場合は、 1 < gcd ( a、n ) < nがnの因数であるため、 nは確実に合成数です。

この定義の根拠は、オイラーの基準の記事で説明されているように、すべての素数 nが上記の式を満たすという事実です。この式は比較的迅速にテストでき、確率的な素数性テストに使用できます。これらのテストは、フェルマーの小定理に基づくテストよりも 2 倍以上強力です。

すべてのオイラー・ヤコビ擬素数は、フェルマー擬素数やオイラー擬素数でもある。カーマイケル数のように、すべての基数に対してオイラー・ヤコビ擬素数となる数は存在しない。ソロベイとシュトラッセンは、すべての合成数nに対して、少なくともn /2 基数nより小さい基数に対して、n はオイラー・ヤコビ擬素数ではないことを示した。^[1]

^{2を底とする最小のオイラー・ヤコビ擬素数は561である。2を底とするオイラー・ヤコビ擬素数のうち25·10 9}未満のものは11347個ある（ OEIS :A047713を参照）（^[2]の1005ページ）。

文献（例えば^[2]）では、上で定義されたオイラー-ヤコビ擬素数は単にオイラー擬素数と呼ばれることが多い。

関数EulerJacobiTest(k)
        2 = 2 です
        k == 1の場合は false を返し
        、そうでない場合はk == 2の場合は true を返し、
        そう
                でない場合は( modPow(a,(k-1)/2,k) == Jacobi(a,k) )の場合は
                        true を返し
                、そうでない場合は
                        false を返します
                。
        終了 終了
終了

• 素数の可能性