強い擬素数

強い擬素数とは、ミラー・ラビン素数判定に合格する合成数です。すべての素数はこの判定に合格しますが、ごく一部の合成数も合格し、それらは「擬素数」になります。

すべての互いに素な基数に対して擬素数となる数(カーマイケル数)が存在するフェルマー擬素数とは異なり、すべての基数に対して強擬素数となる合成数は存在しません。

n = 31697 が確率素数(PRP) であるかどうかを調べたいとします。底a = 3を選び、フェルマーの小定理を参考にして計算します。

${\displaystyle 3^{31696}\equiv 1{\pmod {31697}}}$

これは 31697 がフェルマー PRP (基数 3) であることを示しているので、素数であると考えられます。ここで指数を繰り返し半分にします。

${\displaystyle 3^{15848}\equiv 1{\pmod {31697}}}$

${\displaystyle 3^{7924}\equiv 1{\pmod {31697}}}$

${\displaystyle 3^{3962}\equiv 28419{\pmod {31697}}}$

最初の数回は何も面白い結果は得られません (結果は依然として 31697 を法とする 1 でした) が、指数 3962 では、31697 を法とする 1 でもマイナス 1 でもない結果 (つまり 31696) が見られます。これは、31697 が実際には合成数であることを証明しています (29×1093 に等しい)。素数を法とすると、剰余 1 は 1 とマイナス 1 以外の平方根を持つことはできません。これは、31697 が基数 3 の強い擬素数ではないことを示しています。

別の例として、n = 47197 を選択し、同じ方法で計算します。

${\displaystyle 3^{47196}\equiv 1{\pmod {47197}}}$

${\displaystyle 3^{23598}\equiv 1{\pmod {47197}}}$

${\displaystyle 3^{11799}\equiv 1{\pmod {47197}}}$

この場合、結果は奇数の指数に達するまで 1 (mod 47197) のままです。この状況では、47197 は3 を底とする強い確率素数であると言えます。この PRP は実際には合成数であることが判明しているため (3 以外の底を選択するとわかります)、47197 は 3 を底とする強い擬素数であることがわかります。

最後に、n = 74593 の場合を考えます。次のようになります。

${\displaystyle 3^{74592}\equiv 1{\pmod {74593}}}$

${\displaystyle 3^{37296}\equiv 1{\pmod {74593}}}$

${\displaystyle 3^{18648}\equiv 74592{\pmod {74593}}}$

ここで、74593 を法としてマイナス 1 に達します。これは素数では完全に起こり得る状況です。これが発生すると、(指数がまだ奇数ではないにもかかわらず) 計算を停止し、74593 は3 を底とする強い確率素数 (そして、結局のところ、強い擬似素数) であるとします。

奇数の合成数n = d · 2 ^s + 1 ( dは奇数) は、次の条件を満たす場合、 a を基数とする強(フェルマー)擬素数と呼ばれます。

${\displaystyle a^{d}\equiv 1{\pmod {n}}}$

または

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{ for some }}0\leq r<s.}$

(数n が上記の条件のいずれかを満たし、それが素数であるかどうかまだわからない場合は、それをa を底とする強い確率素数と呼ぶ方が正確です。しかし、 nが素数でないことがわかっている場合は、強い擬似素数という用語を使用できます。)

定義は、a ≡ ±1 (mod n )の場合に自明に満たされるため、これらの自明な基数は除外されることが多いです。

ガイは誤って最初の条件のみで定義を与えているが、これはすべての素数が満たすわけではない。^[1]

a を底とする強擬素数は、常にその底に対するオイラー・ヤコビ擬素数、オイラー擬素数^[2]、フェルマー擬素数であるが、すべてのオイラー擬素数とフェルマー擬素数が強擬素数であるわけではない。カーマイケル数は、いくつかの底に対して強擬素数となることがある (たとえば、561 は 50 を底とする強擬素数である) が、すべての底に対して強擬素数となるわけではない。

合成数nは、nより小さいすべての基数のうち最大で 4 分の 1 に対して強い擬素数である。 ^{[3] [4]}したがって、「強いカーマイケル数」、つまりすべての基数に対して強い擬素数である数は存在しない。したがって、ランダムな基数が与えられた場合、その基数に対して数が強い擬素数である確率は 1/4 未満であり、広く使用されているミラー・ラビン素数性テストの基礎を形成している。失敗する真の確率は一般にはるかに小さい。ポール・エルデシュとカール・ポメランスは1986 年に、ランダムな整数 n がランダムな基数 b に対してミラー・ラビン素数性テストに合格する場合、 n はほぼ確実に素数であることを示した。^[5]例えば、最初の 25,000,000,000 個の正の整数のうち、2 を底とする素数である可能性のある整数は 1,091,987,405 個ありますが、そのうち擬素数は 21,853 個のみで、強擬素数はさらに少なくなります。これは、強擬素数が前者のサブセットであるためです。^[6] しかし、Arnault ^{[7] は、 307 未満のすべての底に対して強擬素数となる 397 桁のカーマイケル数を与えています。このような数が誤っておそらく素数であると宣言される可能性を減らす 1 つの方法は、} Baillie–PSW 素数判定テストのように、 強素数テストとLucas 素数テストを組み合わせることです。

任意の基数に対して、強い擬素数は無限に存在する。^[2]

2を底とする最初の強擬素数は

2047、3277、4033、4681、8321、15841、293​​41、42799、49141、52633、65281、74665、80581、85489、88357、90751、...（OEISのシーケンスA001262）。

3を最初に打った人は

121、703、1891、3281、8401、8911、10585、12403、16531、18721、19345、23521、31621、44287、47197、55969、63139、74593、79003、82513、87913、88573、97567、...（OEISの配列A020229）。

5進数の最初のものは

781、1541、5461、5611、7813、13021、14981、15751、24211、25351、29539、38081、40501、44801、53971、79381、...（OEISの配列A020231）。

基数 4 についてはOEIS :A020230を、基数 6 から 100 についてはOEIS :A020232からOEIS :A020326を参照してください。上記の条件を複数の基数に対してテストすることで、1 つの基数だけを使用する場合よりも、いくぶん強力な素数判定が可能になります。たとえば、2、3、5 の基数に対して同時に強い擬素数となる25·10 ^{9未満の数は 13 個しかありません。これらは[2]}の表 7 にリストされています。そのような最小の数は 25326001 です。つまり、nが 25326001 未満で、nが基数 2、3、5 に対して強い可能性のある素数である場合、nは素数です。

これをさらに進めると、3825123056546413051は、2、3、5、7、11、13、17、19、23の9つの底に対して強い擬素数となる最小の数字です。^{[8] [9]} したがって、nが3825123056546413051未満で、nがこれら9つの底に対して強い確率的素数である場合、nは素数です。

必ずしも素数ではない基数を慎重に選択することで、さらに優れたテストを構築することができます。たとえば、2、325、9375、28178、450775、9780504、1795265022の7つの基数すべてに対して強い擬素数となる合成数は存在しません。 ^[10]${\displaystyle <2^{64}}$