オイラー擬素数

数学において、奇数の 合成 整数 nは、 aとnが互いに素であるとき、aを基底とするオイラー擬素数と呼ばれ、

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

( mod はモジュロ演算を表します)。

この定義の動機は、すべての素数 p が上記の式を満たすという事実であり、これはフェルマーの小定理から演繹できます。フェルマーの定理は、pが素数であり、aと互いに素である場合、a ^{p −1} ≡ 1 (mod p ) であると主張しています。 p >2 が素数であるとすると、p は2 q  + 1 ( qは整数)と表すことができます。したがって、 a ^{(2 q +1) − 1} ≡ 1 (mod  p ) であり、これはa ^{2 q}  − 1 ≡ 0 (mod p ) を意味します。これは、 ( a ^q  − 1)( a ^q + 1) ≡ 0 (mod p )と因数分解でき、 a ^{( p −1)/2} ≡ ±1 (mod  p )と同等です。

この方程式は比較的早くテストすることができ、確率的素数性テストに使用できます。これらのテストは、フェルマーの小定理に基づくテストの 2 倍強力です。

すべてのオイラー擬素数は、フェルマー擬素数でもある。絶対オイラー擬素数、つまり、自分自身と互いに素であるすべての基数に対してオイラー擬素数となる数が存在するため、数がオイラー擬素数であるかどうかに基づいて素数かどうかを明確に判定することはできない。絶対オイラー擬素数は、絶対フェルマー擬素数、またはカーマイケル数の一部であり、最小の絶対オイラー擬素数は1729 = 7×13×19 ( OEISのシーケンスA033181 ) である。

もう少し強力なテストでは、ヤコビ記号を使用して、2つの結果のうちどちらが見つかるかを予測します。結果として得られるオイラー・ヤコビの確率素数テストでは、次のことが検証されます。

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

基本的なオイラーテストと同様に、aとn は互いに素である必要がありますが、そのテストはヤコビ記号 ( a / n ) の計算に含まれており、値が互いに素でない場合は 0 になります。この少し強力なテストは、一部の著者によって単にオイラー確率素数テストと呼ばれています。たとえば、以下に挙げたコブリッツの本の 115 ページ、リーゼルの本の 90 ページ、またはの 1003 ページを参照してください。^[1]

このテストの強度が増した例として、341は底2のオイラー擬素数であるが、オイラー・ヤコビ擬素数ではない。さらに重要なことは、絶対的なオイラー・ヤコビ擬素数は存在しないということである。^{[1] : 1004}

強い確率素数検定はオイラー・ヤコビ検定よりもさらに強力ですが、計算量は同じです。このため、素数検定ソフトウェアは通常、強い検定に基づいています。

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

• 素数の可能性

• M. Koblitz、「数論と暗号学の講座」、Springer-Verlag、1987 年。
• H. Riesel、「素数と因数分解のコンピュータ手法」、Birkhäuser、マサチューセッツ州ボストン、1985 年。