強い擬素数

Composite number which passes Miller–Rabin primality test

強擬素数とは、ミラー・ラビン素数判定を満たす合成数です。すべての素数はこの判定を満たしますが、ごく一部の合成数もこの判定を満たすため、「擬素数」となります。

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

動機と最初の例

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を底とする強確率素数であると言えます。この確率素数は実際には合成数であることが判明しているため（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 つの底だけを使用する場合よりもいくぶん強力な素数判定が可能になります。たとえば、25·10 ⁹未満の数で、同時に 2、3、5 を底とする強い擬素数となるものは 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}}$

最小の強擬素数を底とする1つの

1つの	最小SPSP	1つの	最小SPSP	1つの	最小SPSP	1つの	最小SPSP
1	9	33	545	65	33	97	49
2	2047	34	33	66	65	98	9
3	121	35	9	67	33	99	25
4	341	36	35	68	25	100	9
5	781	37	9	69	35	101	25
6	217	38	39	70	69	102	133
7	25	39	133	71	9	103	51
8	9	40	39	72	85	104	15
9	91	41	21	73	9	105	451
10	9	42	451	74	15	106	15
11	133	43	21	75	91	107	9
12	91	44	9	76	15	108	91
13	85	45	481	77	39	109	9
14	15	46	9	78	77	110	111
15	1687	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81	91	113	57
18	25	50	49	82	9	114	115
19	9	51	25	83	21	115	57
20	21	52	51	84	85	116	9
21	221	53	9	85	21	117	49
22	21	54	55	86	85	118	9
23	169	55	9	87	247	119	15
24	25	56	55	88	87	120	91
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	65
27	121	59	15	91	9	123	85
28	9	60	481	92	91	124	25
29	15	61	15	93	25	125	9
30	49	62	9	94	93	126	25
31	15	63	529	95	1891	127	9
32	25	64	9	96	95	128	49

参考文献

1. Guy ,擬素数. オイラー擬素数. 強擬素数. §A12,数論における未解決問題, 第2版. ニューヨーク: Springer-Verlag, pp. 27-30, 1994.
2. カール・ポメランス、ジョン・L・セルフリッジ、サミュエル・S・ワグスタッフ・ジュニア(1980年7月). 「25·109までの擬素数」(PDF) .計算数学. 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
3. Louis Monier (1980). 「2つの効率的な確率的素数判定アルゴリズムの評価と比較」.理論計算機科学. 12 : 97–108 . doi : 10.1016/0304-3975(80)90007-9 .
4. ラビン、「素数判定のための確率的アルゴリズム」、 数論ジャーナル、12、pp. 128–138、1980年。
5. 「可能性のある素数：その確率は？」2020年10月23日閲覧。
6. 「素数用語集: 推定素数」.
7. F. Arnault (1995年8月). 「複数の基数に対して強擬素数となるカーマイケル数の構築」. Journal of Symbolic Computation . 20 (2): 151– 161. doi : 10.1006/jsco.1995.1042 .
8. Zhenxiang Zhang; Min Tang (2003). 「複数の基数に対する強擬素数の探索 II」.計算数学. 72 (244): 2085– 2097. doi : 10.1090/S0025-5718-03-01545-X .
9. Jiang, Yupeng; Deng, Yingpu (2012). 「最初の9つの素数基数に対する強擬素数」. arXiv : 1207.0063v1 [math.NT].
10. "SPRP Records" . 2015年6月3日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Strong_pseudoprime&oldid=1311034764"