オイラー擬素数
与えられた合同性を満たす奇数の合成数

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

1つの （ n − 1 ） / 2 ≡ ± 1 （ モッド n ） {\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つの結果のうちどちらが見つかるかを予測します。結果として得られるオイラー・ヤコビ確率素数テストは、

1つの （ n − 1 ） / 2 ≡ （ 1つの n ） ≠ 0 （ モッド n ） 。 {\displaystyle 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

参照

参考文献

  1. ^ 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 年。
「https://en.wikipedia.org/w/index.php?title=オイラー擬素数&oldid=1325240531」より取得