フェルマー擬素数

フェルマーの素数判定を満たす合成数

数論において、フェルマー擬素数はフェルマーの小定理から導かれる擬素数の中で最も重要なクラスを構成します。

意味

フェルマーの小定理は、が素数で と互いに素であるとき、 はで割り切れることを述べています。正の整数 に対して、合成整数がを割り切れるとき、は を底とするフェルマー擬素数と呼ばれます。^{[1] ：定義3.32} ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle a^{p-1}-1}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle x}$ ${\displaystyle a^{x-1}-1}$ ${\displaystyle x}$ ${\displaystyle a}$

言い換えれば、合成整数が を底とするフェルマーの素数判定に合格する場合、その合成整数は を底とするフェルマー擬素数である。^[2] 2 を底とするフェルマーの素数判定に合格する数はすべて素数であるという誤った主張は、中国仮説と呼ばれている。 ${\displaystyle a}$ ${\displaystyle a}$

最小の基数 2 のフェルマー擬素数は 341 です。これは 11·31 に等しいため素数ではありませんが、フェルマーの小定理を満たしており、基数 2 のフェルマー素数判定に合格します 。 ${\displaystyle 2^{340}\equiv 1({\bmod {341}})}$

2 を底とする擬素数は、341 がこの性質を持つことを発見したPF SarrusにちなんでSarrus数、そのような数の表を作成したP. PouletにちなんでPoulet 数、あるいはフェルマーティアン( OEISのシーケンスA001567 ) と呼ばれることがあります。

フェルマー擬素数は、しばしば擬素数と呼ばれ、修飾子Fermat が理解されます。

と互いに素であるすべての値に対してフェルマー擬素数となる整数はカーマイケル数と呼ばれる。^{[2] [1] : 定義3.34} ${\displaystyle x}$ ${\displaystyle a}$ ${\displaystyle x}$

プロパティ

分布

任意の基数 に対して、擬素数は無限に存在する。1904年、チポラは を基数とする擬素数を無限に生成する方法を示した。 ととし、 はを割り切れない素数である。するとは合成数となり、 は を基数とする擬素数となる。^{[3] [4]}例えば、と のとき、、、 はを基数とする擬素数となる。 ${\displaystyle a>1}$ ${\displaystyle a>1}$ ${\displaystyle A=(a^{p}-1)/(a-1)}$ ${\displaystyle B=(a^{p}+1)/(a+1)}$ ${\displaystyle p}$ ${\displaystyle a(a^{2}-1)}$ ${\displaystyle n=AB}$ ${\displaystyle a}$ ${\displaystyle a=2}$ ${\displaystyle p=5}$ ${\displaystyle A=31}$ ${\displaystyle B=11}$ ${\displaystyle n=AB=341}$ ${\displaystyle 2}$

実際、1より大きい基数には強擬素数が無限に存在し（ ^[5]の定理1を参照）、カーマイケル数も無限に存在する^[6]が、それらは比較的稀である。2を底とする1000未満の擬素数は3個、100万未満の擬素数は245個、25×10 ⁹未満の擬素数は21853個存在する。この限界未満の2を底とする強擬素数は4842個、カーマイケル数は2163個存在する（^[5]の表1を参照）。

17·257 から始まる連続するフェルマー数の積は底 2 の擬素数であり、すべてのフェルマー合成数とメルセンヌ合成数も同様です。

合成数nがフェルマーテストを通過する確率は、に対してゼロに近づく。具体的には、キムとポメランスは以下を示した。ランダムな奇数がランダムな基数に対するフェルマー擬素数である確率は、 x=10 ^{100に対して2.77·10 −8}未満であり、x≥10 ^{100,000に対して最大で(log x) −197} <10 ^−10,000である。^[7]固定基数bに対して、xまでの擬素数の割合は、xが大きい場合、最大でe ^{-log x log log log x/(2 log log x)}である。^[8] ${\displaystyle n\to \infty }$ ${\displaystyle n\leq x}$ ${\displaystyle 1<b<n-1}$

因数分解

13 個のカーマイケル数 (太字) を含む、60787 までの 60 個のプーレ数の因数分解が次の表に示されています。

（OEISの配列A001567）

プーレ 1～15 341 11 · 31 561 3 · 11 · 17 645 3 · 5 · 43 1105 5 · 13 · 17 1387 19 · 73 1729 7 · 13 · 19 1905 3 · 5 · 127 2047 23 · 89 2465 5 · 17 · 29 2701 37 · 73 2821 7 · 13 · 31 3277 29 · 113 4033 37 · 109 4369 17 · 257 4371 3 · 31 · 47

プーレ 16～30 4681 31 · 151 5461 43 · 127 6601 7 · 23 · 41 7957 73 · 109 8321 53 · 157 8481 3 · 11 · 257 8911 7 · 19 · 67 10261 31 · 331 10585 5 · 29 · 73 11305 5 · 7 · 17 · 19 12801 3 · 17 · 251 13741 7 · 13 · 151 13747 59 · 233 13981 11 · 31 · 41 14491 43 · 337

プーレ 31～45 15709 23 · 683 15841 7 · 31 · 73 16705 5 · 13 · 257 18705 3 · 5 · 29 · 43 18721 97 · 193 19951 71 · 281 23001 3 · 11 · 17 · 41 23377 97 · 241 25761 3 · 31 · 277 29341 13 · 37 · 61 30121 7 · 13 · 331 30889 17 · 23 · 79 31417 89 · 353 31609 73 · 433 31621 103 · 307

プーレ 46～60 33153 3 · 43 · 257 34945 5 · 29 · 241 35333 89 · 397 39865 5 · 7 · 17 · 67 41041 7 · 11 · 13 · 41 41665 5 · 13 · 641 42799 127 · 337 46657 13 · 37 · 97 49141 157 · 313 49981 151 · 331 52633 7 · 73 · 103 55245 3 · 5 · 29 · 127 57421 7 · 13 · 631 60701 101 · 601 60787 89 · 683

全ての約数dが2 ^d − 2を割り切るプーレ数は超プーレ数と呼ばれる。超プーレ数ではないプーレ数は無限に存在する。^[9]

最小のフェルマー擬素数

200以下の各基数aに対する最小の擬素因数を以下の表に示す。色は素因数の個数を示す。本稿冒頭の定義とは異なり、この表ではa未満の擬素数は除外されている。（ a未満の擬素数を認める方法については、OEISのシーケンスA090086を参照のこと。）

（ OEISの配列A007535）

1つの	最小pp	1つの	最小pp	1つの	最小pp	1つの	最小pp
1	4 = 2²	51	65 = 5 · 13	101	175 = 5² · 7	151	175 = 5² · 7
2	341 = 11 · 31	52	85 = 5 · 17	102	133 = 7 · 19	152	153 = 3² · 17
3	91 = 7 · 13	53	65 = 5 · 13	103	133 = 7 · 19	153	209 = 11 · 19
4	15 = 3 · 5	54	55 = 5 · 11	104	105 = 3 · 5 · 7	154	155 = 5 · 31
5	124 = 2² · 31	55	63 = 3² · 7	105	451 = 11 · 41	155	231 = 3 · 7 · 11
6	35 = 5 · 7	56	57 = 3 · 19	106	133 = 7 · 19	156	217 = 7 · 31
7	25 = 5²	57	65 = 5 · 13	107	133 = 7 · 19	157	186 = 2 · 3 · 31
8	9 = 3²	58	133 = 7 · 19	108	341 = 11 · 31	158	159 = 3 · 53
9	28 = 2² · 7	59	87 = 3 · 29	109	117 = 3² · 13	159	247 = 13 · 19
10	33 = 3 · 11	60	341 = 11 · 31	110	111 = 3 · 37	160	161 = 7 · 23
11	15 = 3 · 5	61	91 = 7 · 13	111	190 = 2 · 5 · 19	161	190 = 2 · 5 · 19
12	65 = 5 · 13	62	63 = 3² · 7	112	121 = 11の²	162	481 = 13 · 37
13	21 = 3 · 7	63	341 = 11 · 31	113	133 = 7 · 19	163	186 = 2 · 3 · 31
14	15 = 3 · 5	64	65 = 5 · 13	114	115 = 5 · 23	164	165 = 3 · 5 · 11
15	341 = 11 · 31	65	112 = 2⁴ · 7	115	133 = 7 · 19	165	172 = 2² · 43
16	51 = 3 · 17	66	91 = 7 · 13	116	117 = 3² · 13	166	301 = 7 · 43
17	45 = 3² · 5	67	85 = 5 · 17	117	145 = 5 · 29	167	231 = 3 · 7 · 11
18	25 = 5²	68	69 = 3 · 23	118	119 = 7 · 17	168	169 = 13²
19	45 = 3² · 5	69	85 = 5 · 17	119	177 = 3 · 59	169	231 = 3 · 7 · 11
20	21 = 3 · 7	70	169 = 13²	120	121 = 11の²	170	171 = 3² · 19
21	55 = 5 · 11	71	105 = 3 · 5 · 7	121	133 = 7 · 19	171	215 = 5 · 43
22	69 = 3 · 23	72	85 = 5 · 17	122	123 = 3 · 41	172	247 = 13 · 19
23	33 = 3 · 11	73	111 = 3 · 37	123	217 = 7 · 31	173	205 = 5 · 41
24	25 = 5²	74	75 = 3 · 5²	124	125 = 5³	174	175 = 5² · 7
25	28 = 2² · 7	75	91 = 7 · 13	125	133 = 7 · 19	175	319 = 11 · 19
26	27 = 3³	76	77 = 7 · 11	126	247 = 13 · 19	176	177 = 3 · 59
27	65 = 5 · 13	77	247 = 13 · 19	127	153 = 3² · 17	177	196 = 2² · 7²
28	45 = 3² · 5	78	341 = 11 · 31	128	129 = 3 · 43	178	247 = 13 · 19
29	35 = 5 · 7	79	91 = 7 · 13	129	217 = 7 · 31	179	185 = 5 · 37
30	49 = 7²	80	81 = 3⁴	130	217 = 7 · 31	180	217 = 7 · 31
31	49 = 7²	81	85 = 5 · 17	131	143 = 11 · 13	181	195 = 3 · 5 · 13
32	33 = 3 · 11	82	91 = 7 · 13	132	133 = 7 · 19	182	183 = 3 · 61
33	85 = 5 · 17	83	105 = 3 · 5 · 7	133	145 = 5 · 29	183	221 = 13 · 17
34	35 = 5 · 7	84	85 = 5 · 17	134	135 = 3³ · 5	184	185 = 5 · 37
35	51 = 3 · 17	85	129 = 3 · 43	135	221 = 13 · 17	185	217 = 7 · 31
36	91 = 7 · 13	86	87 = 3 · 29	136	265 = 5 · 53	186	187 = 11 · 17
37	45 = 3² · 5	87	91 = 7 · 13	137	148 = 2² · 37	187	217 = 7 · 31
38	39 = 3 · 13	88	91 = 7 · 13	138	259 = 7 · 37	188	189 = 3³ · 7
39	95 = 5 · 19	89	99 = 3² · 11	139	161 = 7 · 23	189	235 = 5 · 47
40	91 = 7 · 13	90	91 = 7 · 13	140	141 = 3 · 47	190	231 = 3 · 7 · 11
41	105 = 3 · 5 · 7	91	115 = 5 · 23	141	355 = 5 · 71	191	217 = 7 · 31
42	205 = 5 · 41	92	93 = 3 · 31	142	143 = 11 · 13	192	217 = 7 · 31
43	77 = 7 · 11	93	301 = 7 · 43	143	213 = 3 · 71	193	276 = 2² · 3 · 23
44	45 = 3² · 5	94	95 = 5 · 19	144	145 = 5 · 29	194	195 = 3 · 5 · 13
45	76 = 2² · 19	95	141 = 3 · 47	145	153 = 3² · 17	195	259 = 7 · 37
46	133 = 7 · 19	96	133 = 7 · 19	146	147 = 3 · 7²	196	205 = 5 · 41
47	65 = 5 · 13	97	105 = 3 · 5 · 7	147	169 = 13²	197	231 = 3 · 7 · 11
48	49 = 7²	98	99 = 3² · 11	148	231 = 3 · 7 · 11	198	247 = 13 · 19
49	66 = 2 · 3 · 11	99	145 = 5 · 29	149	175 = 5² · 7	199	225 = 3² · 5²
50	51 = 3 · 17	100	153 = 3² · 17	150	169 = 13²	200	201 = 3 · 67

固定基数におけるフェルマー擬素数の一覧n

n	nを底とするフェルマー擬素数の最初のいくつか	OEISシーケンス
1	4、6、8、9、10、12、14、15、16、18、20、21、22、24、25、26、27、28、30、32、33、34、35、36、38、39、40、42、44、45、46、48、49、50、51、52、54、55、56、57、58、60、62、63、64、65、66、68、69、70、72、74、75、76、77、78、80、81、82、84、85、 86、87、88、90、91、92、93、94、95、96、98、99、100、...（すべて複合）	A002808
2	341、561、645、1105、1387、1729、1905、2047、2465、2701、2821、3277、4033、4369、4371、4681、5461、6601、7957、8321、8481、8911、...	A001567
3	91、121、286、671、703、949、1105、1541、1729、1891、2465、2665、2701、2821、3281、3367、3751、4961、5551、6601、7381、8401、8911、...	A005935
4	15、85、91、341、435、451、561、645、703、1105、1247、1271、1387、1581、1695、1729、1891、1905、2047、2071、2465、2701、2821、3133、3277、3367、3683、4033、4369、4371、4681、4795、4859、5461、5551、6601、6643、7957、8321、8481、8695、8911、 9061、9131、9211、9605、9919、...	A020136
5	4、124、217、561、781、1541、1729、1891、2821、4123、5461、5611、5662、5731、6601、7449、7813、8029、8911、9881、...	A005936
6	35、185、217、301、481、1105、1111、1261、1333、1729、2465、2701、2821、3421、3565、3589、3913、4123、4495、5713、6533、6601、8029、8365、8911、9331、9881、...	A005937
7	6、25、325、561、703、817、1105、1825、2101、2353、2465、3277、4525、4825、6697、8321、...	A005938
8	9、21、45、63、65、105、117、133、153、231、273、341、481、511、561、585、645、651、861、949、1001、1105、1281、1365、1387、1417、1541、1649、1661、1729、1785、1905、2047、2169、2465、2501、2701、2821、3145、3171、3201、3277、3605、3641、 4005、4033、4097、4369、4371、4641、4681、4921、5461、5565、5963、6305、6533、6601、6951、7107、7161、7957、8321、8481、8911、9265、9709、9773、9881、9945、...	A020137
9	4、8、28、52、91、121、205、286、364、511、532、616、671、697、703、946、949、1036、1105、1288、1387、1541、1729、1891、2465、2501、2665、2701、2806、2821、2926、3052、3281、3367、3751、4376、4636、4961、5356、5551、6364、6601、6643、7081、 7381、7913、8401、8695、8744、8866、8911、...	A020138
10	9、33、91、99、259、451、481、561、657、703、909、1233、1729、2409、2821、2981、3333、3367、4141、4187、4521、5461、6533、6541、6601、7107、7471、7777、8149、8401、8911、...	A005939
11	10、15、70、133、190、259、305、481、645、703、793、1105、1330、1729、2047、2257、2465、2821、4577、4921、5041、5185、6601、7869、8113、8170、8695、8911、9730、...	A020139
12	65、91、133、143、145、247、377、385、703、1045、1099、1105、1649、1729、1885、1891、2041、2233、2465、2701、2821、2983、3367、3553、5005、5365、5551、5785、6061、6305、6601、8911、9073、...	A020140
13	4、6、12、21、85、105、231、244、276、357、427、561、1099、1785、1891、2465、2806、3605、5028、5149、5185、5565、6601、7107、8841、8911、9577、9637、...	A020141
14	15、39、65、195、481、561、781、793、841、985、1105、1111、1541、1891、2257、2465、2561、2665、2743、3277、5185、5713、6501、6533、6541、7107、7171、7449、7543、7585、8321、9073、...	A020142
15	14、341、742、946、1477、1541、1687、1729、1891、1921、2821、3133、3277、4187、6541、6601、7471、8701、8911、9073、...	A020143
16	15、51、85、91、255、341、435、451、561、595、645、703、1105、1247、1261、1271、1285、1387、1581、1687、1695、1729、1891、1905、2047、2071、2091、2431、2465、2701、2821、3133、3277、3367、3655、3683、4033、4369、4371、4681、4795、4859、5083、 5151、5461、5551、6601、6643、7471、7735、7957、8119、8227、8245、8321、8481、8695、8749、8911、9061、9131、9211、9605、9919、...	A020144
17	4、8、9、16、45、91、145、261、781、1111、1228、1305、1729、1885、2149、2821、3991、4005、4033、4187、4912、5365、5662、5833、6601、6697、7171、8481、8911、...	A020145
18	25、49、65、85、133、221、323、325、343、425、451、637、931、1105、1225、1369、1387、1649、1729、1921、2149、2465、2701、2821、2825、2977、3325、4165、4577、4753、5525、5725、5833、5941、6305、6517、6601、7345、8911、9061、...	A020146
19	6、9、15、18、45、49、153、169、343、561、637、889、905、906、1035、1105、1629、1661、1849、1891、2353、2465、2701、2821、2955、3201、4033、4681、5461、5466、5713、6223、6541、6601、6697、7957、8145、8281、8401、8869、9211、9997、...	A020147
20	21、57、133、231、399、561、671、861、889、1281、1653、1729、1891、2059、2413、2501、2761、2821、2947、3059、3201、4047、5271、5461、5473、5713、5833、6601、6817、7999、8421、8911、...	A020148
21	4、10、20、55、65、85、221、703、793、1045、1105、1852、2035、2465、3781、4630、5185、5473、5995、6541、7363、8695、8965、9061、...	A020149
22	21、69、91、105、161、169、345、483、485、645、805、1105、1183、1247、1261、1541、1649、1729、1891、2037、2041、2047、2413、2465、2737、2821、3241、3605、3801、5551、5565、5963、6019、6601、6693、7081、7107、7267、7665、8119、8365、8421、 8911、9453、…	A020150
23	22、33、91、154、165、169、265、341、385、451、481、553、561、638、946、1027、1045、1065、1105、1183、1271、1729、1738、1749、2059、2321、2465、2501、2701、2821、2926、3097、3445、4033、4081、4345、4371、4681、5005、5149、6253、6369、6533、 6541、7189、7267、7957、8321、8365、8651、8745、8911、8965、9805、...	A020151
24	25、115、175、325、553、575、805、949、1105、1541、1729、1771、1825、1975、2413、2425、2465、2701、2737、2821、2885、3781、4207、4537、6601、6931、6943、7081、7189、7471、7501、7813、8725、8911、9085、9361、9809、...	A020152
25	4、6、8、12、24、28、39、66、91、124、217、232、276、403、426、451、532、561、616、703、781、804、868、946、1128、1288、1541、1729、1891、2047、2701、2806、2821、2911、2926、3052、3126、3367、3592、3976、4069、4123、4207、4564、4636、4686、 5321、5461、5551、5611、5662、5731、5963、6601、7449、7588、7813、8029、8646、8911、9881、9976、...	A020153
26	9、15、25、27、45、75、133、135、153、175、217、225、259、425、475、561、589、675、703、775、925、1035、1065、1147、2465、3145、3325、3385、3565、3825、4123、4525、4741、4921、5041、5425、6093、6475、6525、6601、6697、8029、8695、8911、9073、...	A020154
27	26、65、91、121、133、247、259、286、341、365、481、671、703、949、1001、1105、1541、1649、1729、1891、2071、2465、2665、2701、2821、2981、2993、3146、3281、3367、3605、3751、4033、4745、4921、4961、5299、5461、5551、5611、5621、6305、6533、 6601、7381、7585、7957、8227、8321、8401、8911、9139、9709、9809、9841、9881、9919、...	A020155
28	9、27、45、87、145、261、361、529、561、703、783、785、1105、1305、1413、1431、1885、2041、2413、2465、2871、3201、3277、4553、4699、5149、5181、5365、7065、8149、8321、8401、9841、...	A020156
29	4、14、15、21、28、35、52、91、105、231、268、341、364、469、481、561、651、793、871、1105、1729、1876、1897、2105、2257、2821、3484、3523、4069、4371、4411、5149、5185、5356、5473、5565、5611、6097、6601、7161、7294、8321、8401、8421、8841、 8911、...	A020157
30	49、91、133、217、247、341、403、469、493、589、637、703、871、899、901、931、1273、1519、1537、1729、2059、2077、2821、3097、3277、3283、3367、3577、4081、4097、4123、5729、6031、6061、6097、6409、6601、6817、7657、8023、8029、8401、8911、 9881、…	A020158

詳細情報（基数 31 から 100）については、（OEISのシーケンスA020159 ）から（ OEISのシーケンスA020228）を参照してください。また、150 までのすべての基数については、フェルマー擬素数の表（ドイツ語のテキスト）を参照してください。このページでは、nが 1 または -1（mod n）と一致する基数と擬素数であるとは定義されていません。

基地bそのためにnフェルマー擬素数である

合成数が偶数の場合、は自明な基数 に対してフェルマー擬素数です。合成数が奇数の場合、 は自明な基数 に対してフェルマー擬素数です。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b\equiv 1{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b\equiv \pm 1{\pmod {n}}}$

任意の合成数 に対して、を法とする異なる基数 の数は、フェルマー擬素基数 であり、 ^{[10] ： Thm. 1, p. 1392} ${\displaystyle n}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle b}$

${\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}$

ここで、 は の異なる素因数です。これには自明な基数も含まれます。 ${\displaystyle p_{1},\dots ,p_{k}}$ ${\displaystyle n}$

例えば、 の場合 、この積は です。 の場合、そのような最小の非自明な基数は です。 ${\displaystyle n=341=11\cdot 31}$ ${\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}$ ${\displaystyle n=341}$ ${\displaystyle b=2}$

すべての奇数合成数は、 3のべき乗でない限り、少なくとも2つの非自明な基数を法とするフェルマー擬素数である。^{[10] : Cor. 1, p. 1393} ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

合成数n < 200について、以下はb < nのすべての基数のうち、nがフェルマー擬素数となるものの表です。合成数nがこの表に含まれていない場合（またはnが A209211 列に含まれている場合）、nは nを法とする自明な基数 1 に対してのみ擬素数となります。

n	0 < b < nの基数（nはフェルマー擬素数）	拠点数 OEIS : A063994
9	1、8	2
15	1、4、11、14	4
21	1、8、13、20	4
25	1、7、18、24	4
27	1、26	2
28	1、9、25	3
33	1、10、23、32	4
35	1、6、29、34	4
39	1、14、25、38	4
45	1、8、17、19、26、28、37、44	8
49	1、18、19、30、31、48	6
51	1、16、35、50	4
52	1、9、29	3
55	1、21、34、54	4
57	1、20、37、56	4
63	1、8、55、62	4
65	1、8、12、14、18、21、27、31、34、38、44、47、51、53、57、64	16
66	1、25、31、37、49	5
69	1、22、47、68	4
70	1、11、51	3
75	1、26、49、74	4
76	1、45、49	3
77	1、34、43、76	4
81	1,80	2
85	1、4、13、16、18、21、33、38、47、52、64、67、69、72、81、84	16
87	1、28、59、86	4
91	1、3、4、9、10、12、16、17、22、23、25、27、29、30、36、38、40、43、48、51、53、55、61、62、64、66、68、69、74、75、79、81、82、87、88、90	36
93	1、32、61、92	4
95	1、39、56、94	4
99	1、10、89、98	4
105	1、8、13、22、29、34、41、43、62、64、71、76、83、92、97、104	16
111	1、38、73、110	4
112	1、65、81	3
115	1、24、91、114	4
117	1、8、44、53、64、73、109、116	8
119	1、50、69、118	4
121	1、3、9、27、40、81、94、112、118、120	10
123	1、40、83、122	4
124	1、5、25	3
125	1、57、68、124	4
129	1、44、85、128	4
130	1、61、81	3
133	1、8、11、12、18、20、26、27、30、31、37、39、45、46、50、58、64、65、68、69、75、83、87、88、94、96、102、103、106、107、113、115、121、122、125、132	36
135	1、26、109、134	4
141	1、46、95、140	4
143	1、12、131、142	4
145	1、12、17、28、41、46、57、59、86、88、99、104、117、128、133、144	16
147	1、50、97、146	4
148	1、121、137	3
153	1、8、19、26、35、53、55、64、89、98、100、118、127、134、145、152	16
154	1、23、67	3
155	1、61、94、154	4
159	1、52、107、158	4
161	1、22、139、160	4
165	1、23、32、34、43、56、67、76、89、98、109、122、131、133、142、164	16
169	1、19、22、23、70、80、89、99、146、147、150、168	12
171	1、37、134、170	4
172	1、49、165	3
175	1、24、26、51、74、76、99、101、124、149、151、174	12
176	1、49、81、97、113	5
177	1、58、119、176	4
183	1、62、121、182	4
185	1、6、31、36、38、43、68、73、112、117、142、147、149、154、179、184	16
186	1、97、109、157、163	5
187	1、67、120、186	4
189	1、55、134、188	4
190	1、11、61、81、101、111、121、131、161	9
195	1、14、64、79、116、131、181、194	8
196	1、165、177	3

より詳しい情報（n = 201～5000）については、b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999)（擬素数表 16～4999）を参照してください。上記のリストとは異なり、このページでは底 1 とn -1 は除外されています。p が素数の場合、 p 2^が底b のフェルマー擬素数となるのは、 pが底bのヴィーフェリッヒ素数となる場合のみです 。例えば、1093 ² = 1194649 は底 2 のフェルマー擬素数であり、11 ² = 121 は底 3 のフェルマー擬素数です。

nに対するbの値の数は（n が素数の場合、すべてのb はフェルマーの小定理を満たすため、 bの値の数はn − 1でなければならない）

1、1、2、1、4、1、6、1、2、1、10、1、12、1、4、1、16、1、18、1、4、1、22、1、4、1、2、3、28、1、30、1、4、1、4、1、36、1、4、1、40、1、42、1、8、1、46、1、6、1 、...（OEISのシーケンスA063994）

nがbを底とする擬素数（または素数） となる最小の底b > 1は

2、3、2、5、2、7、2、9、8、11、2、13、2、15、4、17、2、19、2、21、8、23、2、25、7、27、26、9、2、31、2、33、10、35、6、37、2、39、14、41、2、43、2、45、8、47、2、49、18、51 、...（OEISのシーケンスA105222）

与えられたnに対するbの値の数は、 ( n )で割り切れる。つまり、A000010( n )=1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,42,20,...となる。商は任意の自然数でよく、nが素数または整数の場合にのみ商=1となる。カーマイケル数(561、1105、1729、2465、2821、6601、8911、10585、15841、... A002997) n が次の数列にある場合のみ、商 = 2 になります: 4、6、15、91、703、1891、2701、11305、12403、13981、18721、... A191311。) ${\displaystyle \varphi }$

bのk個の値と擬素数となる最小の数は（そのような数が存在しない場合は0）である。

1、3、28、5、66、7、232、45、190、11、276、13、1106、0、286、17、1854、19、3820、891、2752、23、1128、595、2046、0、532、29、1770、31、9952、425、1288、0、2486、37、8474、0、742、41、3486、43、7612、5589、2356、47、13584、325、9850、0、...（シーケンスOEISのA064234 ) ( kが偶数であり、平方数のトータンでない場合に限り、この数列のk番目の項は 0 になります。)

弱擬素数

を満たす合成数nは、 bを底とする弱擬素数と呼ばれる。任意のbを底とするフェルマー擬素数は弱擬素数であり、bと互いに素であるすべての弱擬素数はフェルマー擬素数である。しかし、この定義では、 bと互いに素ではない擬素数も許容される。^[11] 例えば、2 を底とする最小の偶数弱擬素数は 161038 である（OEISのシーケンスA006935を参照）。 ${\displaystyle b^{n}\equiv b{\pmod {n}}}$

基数b = 1、2、...に対する最も弱い擬素数は次のとおりです。

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... OEIS : A000790

カーマイケル数はすべての基数に対して弱擬素数であるため、このリストのすべての項は最小のカーマイケル数である 561 以下である。561 = 3⋅11⋅17 を除いて、上記の数列には半素数のみ出現できる。561 未満の半素数がすべて出現するわけではない。561未満の半素数pq ( p ≤ q ) が上記の数列に出現するのは、 p − 1 がq − 1 を割り切る場合のみである ( OEISの数列A108574を参照)。基数bに対する最小のフェルマー擬素数( bを超える必要もない) ( OEISの数列A090086を参照) は通常は半素数であるが、常にそうであるとは限らない。最初の反例は A090086(648) = 385 = 5 × 7 × 11 である。

n > bが必要な場合、最も弱い擬素数（b = 1、2、...の場合）は次のようになります。

4、341、6、6、10、10、14、9、12、15、15、22、21、15、21、20、34、25、38、21、28、33、33、25、28、27、39、36、35、49、 49、33、44、35、45、42、45、39、57、52、82、66、77、45、55、69、65、49、56、51、... OEIS : A239293

オイラー・ヤコビ擬素数

もう一つのアプローチは、より洗練された擬素数の概念、例えば、カーマイケル数に相当するものが存在しない強擬素数やオイラー・ヤコビ擬素数などを用いることである。この考え方は、ソロベイ・シュトラッセン素数判定、ベイリー・PSW素数判定、ミラー・ラビン素数判定といった確率的アルゴリズムにつながり、いわゆる「産業グレード素数」を生成する。産業グレード素数とは、素数であることが「証明」（厳密に証明）されていないものの、ミラー・ラビン判定などの、失敗確率がゼロではないが任意に低い判定を受けている整数である。

アプリケーション

このような擬素数の希少性は、実用上重要な意味合いを持つ。例えば、RSAなどの公開鍵暗号アルゴリズムでは、大きな素数を迅速に発見する能力が求められる。素数を生成するための一般的なアルゴリズムは、ランダムな奇数を生成し、それらが素数かどうかを判定することである。しかし、決定論的な素数判定は時間がかかる。もしユーザーが、発見された数が素数ではなく擬素数であるという、ごくわずかな確率を許容できるのであれば、はるかに高速で簡便なフェルマー素数判定を使用することができる。

参考文献

1. サミュエル・S・ワグスタッフ・ジュニア(2013). 『因数分解の喜び』 プロビデンス、ロードアイランド州: アメリカ数学協会. ISBN 978-1-4704-1048-3。
2. Desmedt, Yvo (2010). 「暗号化スキーム」. Atallah, Mikhail J. ; Blanton, Marina (編).アルゴリズムと計算理論ハンドブック：特別なトピックとテクニック. CRC Press. pp.  10– 23. ISBN 978-1-58488-820-8。
3. パウロ・リーベンボイム(1996). 『素数記録の新書』ニューヨーク:シュプリンガー・フェアラーク108ページ. ISBN 0-387-94457-5。
4. 浜畑義則;國分裕也（2007）． 「Cipolla Pseudoprimes」(PDF)。整数シーケンスのジャーナル。10（8）。
5. ポメランス, カール;セルフリッジ, ジョン・L.;ワグスタッフ, サミュエル・S・ジュニア(1980年7月). 「25·109までの擬素数」(PDF) .計算数学. 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 . 2005年3月4日時点のオリジナルよりアーカイブ(PDF) .
6. Alford, WR ; Granville, Andrew ; Pomerance, Carl (1994). 「カーマイケル数は無限に存在する」(PDF) . Annals of Mathematics . 140 (3): 703– 722. doi :10.2307/2118576. JSTOR 2118576. 2005年3月4日時点のオリジナルより アーカイブ(PDF) .
7. Kim, Su Hee; Pomerance, Carl (1989). 「ランダムな確率素数が合成素数である確率」.計算数学. 53 (188): 721– 741. doi :10.2307/2008733. JSTOR  2008733.
8. ポメランス[81]は[1]の2.1節で引用されている。
9. Sierpinski, W. (1988-02-15)、「第5章7」、A. Schinzel編『初等数論』 、North-Holland Mathematical Library (第2版)、アムステルダム: North Holland、p. 232、ISBN 9780444866622
10. Robert Baillie; Samuel S. Wagstaff Jr. (1980年10月). "Lucas Pseudoprimes" (PDF) . Mathematics of Computation . 35 (152): 1391– 1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518. 2006年9月6日時点のオリジナルより アーカイブ(PDF) .
11. ミション、ジェラール・P. (2003年11月19日). 「擬素数、弱擬素数、強擬素数、素数性」. Numericana . 2018年4月21日閲覧。

外部リンク

• ^{WF Galway と Jan Feitsma、「2 を底とする擬素数の表と関連データ」（因数分解、強擬素数、カーマイケル数を含む、2 64}未満の 2 を底とするすべての擬素数の包括的なリスト）
• 擬素数の研究

「https://en.wikipedia.org/w/index.php?title=フェルマー擬素数&oldid=1320899104」より取得