フェルマー擬素数

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

フェルマーの小定理は、 「pが素数でa がpと互いに素である場合、a ^{p −1}  − 1 はpで割り切れる」と述べています。正の整数aについて、合成整数x がa ^{x −1} − 1を割り切る場合 、x はa を底とするフェルマー擬素数と呼ばれます。 ^{[1] ：定義3.32} 言い換えると、合成整数は、a を底とするフェルマー擬素数であるためには、それがa を底とするフェルマー素数テストに合格する必要があります。^[2]フェルマーの素数テストに合格する数はすべて素数であるという誤った主張は、中国仮説と呼ばれています。

最小の基数 2 のフェルマー擬素数は 341 です。これは 11·31 に等しいため素数ではありませんが、フェルマーの小定理 2 ³⁴⁰ ≡ 1 (mod 341) を満たしており、 基数 2 のフェルマー素数判定に合格します。

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

フェルマー擬素数は、修飾子Fermatが理解される擬素数と呼ばれることがよくあります。

整数xがフェルマー擬素数であり、その整数aがxと互いに素であるような場合、その整数xはカーマイケル数と呼ばれる。^{[2] [1] : 定義3.34}

a > 1 を底とする任意の擬素数は無限に存在します。1904 年に、 Cipolla はa > 1 を底とする無限の擬素数を生成する方法を示しました。A = ( a p - 1)/( a - 1)、B = ( a p + 1)/( a + 1) とします。^ここでpはa ( a ² - 1 )を割り切れない素数^です。するとn = AB は合成数となり、a を底とする擬素数となります。^{[3] [4]}たとえば、a = 2 でp = 5 の場合、A = 31、B = 11、n = 341 は 2 を底とする擬素数となります。

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

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

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

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

（OEISの配列A001567）

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

200 未満の各基数aに対する最小の擬素数は、次の表のとおりです。色は素因数の数を示しています。記事の冒頭の定義とは異なり、a未満の擬素数は表では除外されています。( a未満の擬素数を許可する方法については、OEIS : A090086を参照してください)

（OEISの配列A007535）

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

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

任意の合成数 に対して、を法とする異なる基数（はフェルマー擬素数基数）の数は^{[9] ： 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つの非自明な基数を法とするフェルマー擬素数である。^{[9] : Cor. 1、p. 1393}${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

合成数n < 200 の場合、以下はnがフェルマー擬素数であるすべての基数b < nの表です。合成数nが表にない場合 (またはn がシーケンス A209211 にある場合)、n はnを法とする自明な基数 1 に対してのみ擬素数です。

詳しい情報 ( n = 201 から 5000) については、^{[10] を参照してください。このページでは、} nが 1 または -1 (mod n )と合同な基数に対して擬素数であるとは定義されていません。 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、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)、商 = 2 となるのは、n が次の数列にある場合のみ: 4、6、15、91、703、1891、2701、11305、12403、13981、18721、... A191311) ${\displaystyle \varphi}$

bのn個の値を持つ最小の数は（そのような数が存在しない場合は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 ) ( nが偶数で平方数のトーティエントでない場合に限り、この数列のn番目の項は 0 になります)

を満たす合成数n は、 b を底とする弱い擬素数と呼ばれる。 a を底とする擬素数 (通常の定義による) はこの条件を満たす。逆に、底と互いに素である弱い擬素数は通常の意味での擬素数であるが、そうでない場合はそうでないこともある。^[11] b = 1、2、... を 底とする最も弱い擬素数は以下のとおりである。${\displaystyle b^{n}\equiv b{\pmod {n}}}$

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、4、4、6、46、4、4、10 、... (OEIS のシーケンスA000790 )

すべての項は、最小のカーマイケル数 561 以下です。561 を除いて、上記の数列には半素数のみが現れますが、561 未満の半素数がすべて現れるわけではありません。561 未満の半素数pq ( p ≤ q ) は、 p − 1 がq − 1 を割り切る場合にのみ、上記の数列に現れます。( OEIS :A108574を参照) また、 n を底とする最小の擬素数( n を超える必要もない) ( 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 ）

カーマイケル数はすべての基数に対して弱い擬素数です。

2を底とする最小の偶弱擬素数は161038です（OEIS：A006935を参照）。

もう 1 つのアプローチは、より洗練された擬素数の概念、たとえば、カーマイケル数に相当するものがない強擬素数やオイラー・ヤコビ擬素数を使用することです。これにより、ソロベイ・シュトラッセン素数テスト、ベイリー・PSW 素数テスト、ミラー・ラビン素数テストなどの確率的アルゴリズムが生まれ、いわゆるインダストリアル グレードの素数が生成されます。インダストリアル グレードの素数とは、素数が「認定」されていない (厳密に証明されていない) 整数ですが、ミラー・ラビン テストなどのテストを受けており、失敗する確率はゼロではないものの、任意に低い値になっています。

このような擬素数が稀であることは、実用上重要な意味を持ちます。たとえば、RSAなどの公開鍵暗号アルゴリズムでは、大きな素数を素早く見つける能力が必要です。素数を生成する通常のアルゴリズムは、ランダムな奇数を生成し、それらが素数かどうかをテストすることです。しかし、決定論的な素数テストは時間がかかります。見つかった数が素数ではなく擬素数である可能性がいくらか低くても許容できる場合は、はるかに高速で簡単なフェルマー素数テストを使用できます。

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