オイラー擬素数

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

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つの結果のうちどちらが見つかるかを予測します。結果として得られるオイラー・ヤコビ確率素数テストは、

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

基本的なオイラー検定と同様に、aとnは互いに素であることが求められますが、この検定はヤコビ記号（a / n ）の計算に含まれており、互いに素でない場合、ヤコビ記号の値は0になります。このやや強力な検定は、一部の著者によって単にオイラー確率素数検定と呼ばれています。例えば、下記に挙げたコブリッツの著書の115ページ、リーゼルの著書の90ページ、または^{[1]の1003ページを参照してください。}

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

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

実装ルア

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

例

n	nを底とするオイラー擬素数
1	すべての奇数の合成数: 9、15、21、25、27、33、35、39、45、49、51、55、57、63、65、69、75、77、81、85、87、91、93、95、99、...
2	341、561、1105、1729、1905、2047、2465、3277、4033、4681、5461、6601、8321、8481、...
3	121、703、1541、1729、1891、2465、2821、3281、4961、7381、8401、8911、...
4	341、561、645、1105、1387、1729、1905、2047、2465、2701、2821、3277、4033、4369、4371、4681、5461、6601、7957、8321、8481、8911、...
5	217、781、1541、1729、5461、5611、6601、7449、7813、...
6	185、217、301、481、1111、1261、1333、1729、2465、2701、3421、3565、3589、3913、5713、6533、8365、...
7	25、325、703、817、1825、2101、2353、2465、3277、4525、6697、8321、...
8	9、21、65、105、133、273、341、481、511、561、585、1001、1105、1281、1417、1541、1661、1729、1905、2047、2465、2501、3201、3277、3641、4033、4097、4641、4681、4921、5461、6305、6533、6601、7161、8321、8481、9265、9709、...
9	91、121、671、703、949、1105、1541、1729、1891、2465、2665、2701、2821、3281、3367、3751、4961、5551、6601、7381、8401、8911、...
10	9、33、91、481、657、1233、1729、2821、2981、4187、5461、6533、6541、6601、7777、8149、8401、...
11	133、305、481、645、793、1729、2047、2257、2465、4577、4921、5041、5185、8113、...
12	65、91、133、145、247、377、385、1649、1729、2041、2233、2465、2821、3553、6305、8911、9073、...
13	21、85、105、561、1099、1785、2465、5149、5185、7107、8841、8911、9577、9637、...
14	15、65、481、781、793、841、985、1541、2257、2465、2561、2743、3277、5185、5713、6533、6541、7171、7449、7585、8321、9073、...
15	341、1477、1541、1687、1729、1921、3277、6541、9073、...
16	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、...
17	9、91、145、781、1111、1305、1729、2149、2821、4033、4187、5365、5833、6697、7171、...
18	25、49、65、133、325、343、425、1105、1225、1369、1387、1729、1921、2149、2465、2977、4577、5725、5833、5941、6305、6517、6601、7345、...
19	9、45、49、169、343、561、889、905、1105、1661、1849、2353、2465、2701、3201、4033、4681、5461、5713、6541、6697、7957、8145、8281、8401、9997、...
20	21、57、133、671、889、1281、1653、1729、1891、2059、2413、2761、3201、5461、5473、5713、5833、6601、6817、7999、...
21	65、221、703、793、1045、1105、2465、3781、5185、5473、6541、7363、8965、9061、...
22	21、69、91、105、161、169、345、485、1183、1247、1541、1729、2041、2047、2413、2465、2821、3241、3801、5551、7665、9453、...
23	33、169、265、341、385、481、553、1065、1271、1729、2321、2465、2701、2821、3097、4033、4081、4345、4371、4681、5149、6533、6541、7189、7957、8321、8651、8745、8911、9805、...
24	25、175、553、805、949、1541、1729、1825、1975、2413、2465、2701、3781、4537、6931、7501、9085、9361、...
25	217、561、781、1541、1729、1891、2821、4123、5461、5611、5731、6601、7449、7813、8029、8911、9881、...
26	9、25、27、45、133、217、225、475、561、589、703、925、1065、2465、3325、3385、3565、3825、4741、4921、5041、5425、6697、8029、9073、...
27	65、121、133、259、341、365、481、703、1001、1541、1649、1729、1891、2465、2821、2981、2993、3281、4033、4745、4921、4961、5461、6305、6533、7381、7585、8321、8401、8911、9809、9841、9881、...
28	9、27、145、261、361、529、785、1305、1431、2041、2413、2465、3201、3277、4553、4699、5149、7065、8321、8401、9841、...
29	15、21、91、105、341、469、481、793、871、1729、1897、2105、2257、2821、4371、4411、5149、5185、5473、5565、6097、7161、8321、8401、8421、8841、...
30	49、133、217、341、403、469、589、637、871、901、931、1273、1537、1729、2059、2077、2821、3097、3277、4081、4097、5729、6031、6061、6097、6409、6817、7657、8023、8029、8401、9881、...

最小オイラー擬素数を底とするn

n	最小EPSP	n	最小EPSP	n	最小EPSP	n	最小EPSP
1	9	33	545	65	33	97	21
2	341	34	21	66	65	98	9
3	121	35	9	67	33	99	25
4	341	36	35	68	25	100	9
5	217	37	9	69	35	101	25
6	185	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	65	44	9	76	15	108	91
13	21	45	133	77	39	109	9
14	15	46	9	78	77	110	111
15	341	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81	91	113	21
18	25	50	21	82	9	114	115
19	9	51	25	83	21	115	57
20	21	52	51	84	85	116	9
21	65	53	9	85	21	117	49
22	21	54	55	86	65	118	9
23	33	55	9	87	133	119	15
24	25	56	33	88	87	120	77
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	33
27	65	59	15	91	9	123	85
28	9	60	341	92	21	124	25
29	15	61	15	93	25	125	9
30	49	62	9	94	57	126	25
31	15	63	341	95	141	127	9
32	25	64	9	96	65	128	49

参照

素数の可能性

参考文献

^ ab Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (1980年7月). 「25·109までの擬素数」(PDF) .計算数学. 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210.

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

[PSW-1] Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (1980年7月). 「25·109までの擬素数」(PDF) .計算数学. 35 (151): 1003– 1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210.