ルーカス擬素数

ルーカス擬素数とフィボナッチ擬素数は、すべての素数とごく少数の合成数が合格する特定のテストに合格する合成整数 です。この場合、あるルーカス数列に対する基準です。

_{ベイリーとワグスタッフは}ルーカス擬素数を次のように定義する。^[1]整数PとQ （ P > 0かつ）が与えられたとき、 Uk（P、Q）とVk（P、Q ）_を対応するルーカス列とする。 ${\displaystyle D=P^{2}-4Q}$

nを正の整数とし、をヤコビ記号とする。定義 ${\displaystyle \left({\tfrac {D}{n}}\right)}$

${\displaystyle \delta (n)=n-\left({\tfrac {D}{n}}\right).}$

n がQ を割り切れない素数である場合、次の合同条件が成立します。

この合同が成り立たない場合、nは素数ではありません。nが合成数の場合、この合同は通常成り立ちません。^{[1]これらは、}素数判定においてルーカス数列を有用にする重要な事実です。

合同式( 1 )はフロベニウス擬素数を定義する2つの合同式のうちの1つを表す。したがって、すべてのフロベニウス擬素数はベイリー・ワグスタッフ・ルーカス擬素数でもあるが、その逆は必ずしも成り立たない。

参考文献としては、BressoudとWagonの著書の第8章（Mathematicaコード付き）^[2] 、 CrandallとPomeranceの著書の142～152ページ^[3]、Ribenboimの著書の53～74ページ^{[4]などが挙げられます。}

与えられた( P,Q )ペアに対するルーカス素数とは、上の式(1)が成り立つ任意の正の整数nである( [ 1 ] 1398ページを参照⁾。

与えられた( P,Q )ペアに対するルーカス擬素数は、式( 1 )が成り立つ正の合成整数nである( ^[1] 1391ページ を参照)。

ルーカスの素数検定は、ヤコビ記号が−1となるようにDを選択した場合に最も有用である（ ^{[1]の1401～1409ページ、 [5]}の1024ページ、または^[2]の266～269ページを参照 ）。これは、ルーカス検定とベイリー–PSW素数検定などの強い擬似素数検定を組み合わせる場合に特に重要である。通常、実装ではこの条件を保証するパラメータ選択方法（ ^[1]で推奨され、以下で説明するセルフリッジ法など）を使用する。 ${\displaystyle \left({\tfrac {D}{n}}\right)}$

すると式（１）は ${\displaystyle \left({\tfrac {D}{n}}\right)=-1,}$

合同( 2 )が偽であれば、これはnが合成数であることの証明となる。

合同 ( 2 ) が真であれば、nはルーカスの確率的素数です。この場合、n は素数かルーカス擬素数です。合同 ( 2 ) が真であれば、n は素数である可能性が高い (これは確率的素数という用語の根拠となります) が、これはnが素数であることの証明にはなりません。他の確率的素数判定テストの場合と同様に、異なるD、P、Qで追加のルーカス テストを実行すると、テストの 1 つでnが合成数であることが証明されない限り、 nが素数であるという確信が高まります。

例: P = 3、Q = −1、D = 13 の場合、 UのシーケンスはOEIS : A006190 : U ₀ = 0、U ₁ = 1、U ₂ = 3、U ₃ = 10 などと なります。

まず、n = 19とします。ヤコビ記号は-1なので、δ( n ) = 20、U ₂₀ = 6616217487 = 19·348221973となり、 ${\displaystyle \left({\tfrac {13}{19}}\right)}$

${\displaystyle U_{20}=6616217487\equiv 0{\pmod {19}}.}$

したがって、19 はこの ( P, Q ) ペアのルーカス確率素数です。この場合、19 は素数なので、ルーカス擬素数 ではありません。

次の例では、n = 119とします。 = −1となり、次のように計算できます。 ${\displaystyle \left({\tfrac {13}{119}}\right)}$

${\displaystyle U_{120}\equiv 0{\pmod {119}}.}$

しかし、119 = 7·17 は素数ではないので、119 はこの ( P, Q ) ペアのルーカス擬素数です。実際、119 はP = 3、Q = −1 の最小の擬素数です。

以下で説明するように、与えられたnに対して式（ 2 ）をチェックするためには、Uシーケンスの最初のn + 1項をすべて計算する必要はない。

Q = −1とすると、 P = 1, 2, 3, ... に対する最小のルーカス擬素数は

323、35、119、9、9、143、25、33、9、15、123、35、9、9、15、129、51、9、33、15、21、9、9、49、15、 39、9、35、49、15、9、9、33、51、15、9、35、85、39、9、9、21、25、51、9、143、33、119、9、9、 51、33、95、9、15、301、25、9、9、15、49、155、9、 399、15、33、9、9、49、15、119、9、...

ここで、が奇数である形式に因数分解します。 ${\displaystyle \delta (n)=n-\left({\tfrac {D}{n}}\right)}$${\displaystyle d\cdot 2^{s}}$${\displaystyle d}$

与えられた ( P, Q ) ペアに対する強いルーカス擬素数は、GCD( n, D ) = 1 を満たす奇数の合成数nであり、次の条件の 1 つを満たす。

${\displaystyle U_{d}\equiv 0{\pmod {n}}}$

または

${\displaystyle V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}}$

0 ≤ r < sの場合、1396ページを参照。^[1]強いルーカス擬素数は（同じ ( P, Q ) ペアに対して）ルーカス擬素数でもあるが、その逆は必ずしも真ではない。したがって、強いテストは式 ( 1 ) よりも厳密な素数判定である。

強いルーカス擬素数は無限に存在するため、ルーカス擬素数も無限に存在する。^[1]の定理7は、と を互いに素な正の整数とし、 は正であるが平方ではないとする。すると、を超えない強いルーカス擬素数の数がより大きくなるような正の定数（とに依存）が存在し、が十分に大きい場合である。 ${\displaystyle P}$${\displaystyle Q}$${\displaystyle P^{2}-4Q}$${\displaystyle c}$${\displaystyle P}$${\displaystyle Q}$${\displaystyle x}$${\displaystyle c\cdot \log x}$${\displaystyle x}$

Q = −1 と設定すると、はP -フィボナッチ数列、P -ルーカス数列となり、擬素数は基数Pの強いルーカス擬素数と呼ぶことができます。たとえば、P = 1、2、3、... の場合の最も強くないルーカス擬素数は 4181、169、119、... です。 ${\displaystyle U_{n}}$${\displaystyle V_{n}}$

超強ルーカス擬素数 [ ^{6]は、パラメータ（} P、Q） の集合に対してQ = 1であり、以下の条件の1つを満たす 強ルーカス擬素数である。

${\displaystyle U_{d}\equiv 0{\pmod {n}}{\text{ および }}V_{d}\equiv \pm 2{\pmod {n}}}$

または

${\displaystyle V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}}$

いくつかについて。非常に強いルーカス擬素数も、同じペアの強いルーカス擬素数です。 ${\displaystyle 0\leq r<s-1}$${\displaystyle (P,Q)}$

素数であるかどうかのテストを始める前に、通常は、素数かどうかをテストする数nが奇数であり、完全な平方数ではなく、ある都合のよい限界未満の小さな素数で割り切れないことを確認します。完全な平方数は、平方根に対する ニュートン法を使用して簡単に検出できます。

δ( n ) = n + 1となるように、ヤコビ記号のルーカス列を選択します。 ${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

nが与えられた場合、 Dを選択する 1 つの方法は、となる 5、−7、9、−11、... というシーケンスで最初のD を試行錯誤で見つけることです。 に注意してください。 ( Dとnに共通の素因数がある場合、)。 このD値のシーケンスでは、ヤコビ記号が −1 である D 値に遭遇するまでに試さなければならないD値の平均数は約 1.79 です。 ^{[1] p. 1416 を参照してください。} Dが得られたら、と を設定します。 n にPまたはQと共通の素因数がないことを確認することをお勧めします。 D、P、およびQを選択するこの方法は、John Selfridgeによって提案されました。 ${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$${\displaystyle \left({\tfrac {k}{n}}\right)\left({\tfrac {-k}{n}}\right)=-1}$${\displaystyle \left({\tfrac {D}{n}}\right)=0}$${\displaystyle P=1}$${\displaystyle Q=(1-D)/4}$

(この検索は、 nが正方である場合は決して成功しません。逆に、成功した場合は、nが正方ではないことが証明されます。したがって、最初のいくつかの検索ステップがすべて失敗するまで n の正方性のテストを遅らせることで、時間を節約できます。)

D、P、Qが与えられれば、と を段階的に素早く計算できる再帰関係があります。ルーカス数列 § その他の関係を参照してください。まず、 ${\displaystyle U_{n+1}}$${\displaystyle V_{n+1}}$${\displaystyle O(\log _{2}n)}$

${\displaystyle U_{1}=1}$

${\displaystyle V_{1}=P=1}$

まず、再帰関係を使って、1ステップで からへの添え字を2倍にすることができます。${\displaystyle k}$${\displaystyle 2k}$

${\displaystyle U_{2k}=U_{k}\cdot V_{k}}$

${\displaystyle V_{2k}=V_{k}^{2}-2Q^{k}={\frac {V_{k}^{2}+DU_{k}^{2}}{2}}}$。

次に、繰り返しを使って添え字を1ずつ増やすことができる。

${\displaystyle U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2}$

${\displaystyle V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2}$。

が奇数の場合、 に置き換えます。これは偶数なので、2 で割ることができます。 の分子も同様に処理されます。( nを追加しても、 nを法とする結果は変わりません。) Uシーケンスで計算する各項に対して、 Vシーケンスの対​​応する項を計算することに注意してください。 処理を進めながら、 Qの同じ対応する累乗も計算します。 ${\displaystyle P\cdot U_{2k}+V_{2k}}$${\displaystyle P\cdot U_{2k}+V_{2k}+n}$${\displaystyle V_{2k+1}}$

各段階で、、 、および、 mod nの累乗を削減します。 ${\displaystyle U}$${\displaystyle V}$${\displaystyle Q}$

nの 2 進展開のビットを使用して、 Uシーケンスのどの項を計算するかを決定します。たとえば、n +1 = 44 (= 2 進数では 101100) の場合、左から右に 1 ビットずつ取ると、計算するインデックスのシーケンスが得られます。1 ₂ = 1、10 ₂ = 2、100 ₂ = 4、101 2 ₌ 5、1010 _{2 = 10、1011 2} = 11、10110 ₂ = 22、101100 ₂ = 44。したがって、U ₁、U ₂、U ₄、U ₅、U ₁₀、U ₁₁、U ₂₂、およびU ₄₄を計算します。また、 Q ¹、Q ²、Q ⁴、Q ⁵、Q ¹⁰、Q ¹¹、Q ²²、Q ⁴⁴とともに、Vシーケンス内の同じ番号の項も計算します。

計算が終わると、U _n+1、V _n+1、Q ⁿ⁺¹ (mod n )が計算されます。次に、 U _n+1の既知の値を使用して合同性( 2 )を確認します。

D、P、Qを上記のように選択すると、最初の10個のルーカス擬素数は（ ^[1]の1401ページを参照）、323、377、1159、1829、3827、5459、5777、9071、9179、10877（OEISのシーケンスA217120） となる。

ルーカス テストの 強力なバージョンも同様の方法で実装できます。

D、P、Qが上記のように選択されると、最初の10個の強いルーカス擬素数は、5459、5777、10877、16109、18971、22499、24569、25199、40309、58519（OEISのシーケンスA217255） になります。

超強力なルーカス擬素数のリストを計算するには、 と設定します。次に、P = 3、4、5、6、... を試して、 の値が見つかり、ヤコビ記号 が となるまで続けます。このD、P、およびQ を選択する方法を使用すると、最初の 10 個の超強力なルーカス擬素数は、989、3239、5777、10877、27971、29681、30739、31631、39059、および 72389 になります ( OEISのシーケンスA217719 )。 ${\displaystyle Q=1}$${\displaystyle D=P^{2}-4Q}$${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

合同( 2 )が真であることを確認したら、追加の計算コストをほとんどかけずに確認できる追加の合同条件があります。nが合成数である場合、これらの追加条件はその事実を発見するのに役立つ可能性があります。

nが奇数の素数で、の場合には、次の式が成り立ちます（^[1]の1392ページの式2を参照）。 ${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$

この合同条件は、定義上、ルーカス素数確率テストの一部ではありませんが、前述のように、V _n+1の値はU _n+1を計算する過程で計算されるため、この条件を確認することはほぼ自由です。

合同式( 2 )または( 3 )のいずれかが偽であれば、 nは素数ではないことが証明される。これらの合同式が両方とも真であれば、合同式( 2 )のみを調べた場合よりもnが素数である可能性がさらに高くなる。

もしセルフリッジの方法（上記）でD、P、Q を選ぶ際にQ = −1に設定されていたら、 DとPは変化せず、P = Q = 5となるようにPとQ を調整できる（ルーカス数列-代数関係を参照）。 この強化された方法をPとQ を選ぶために使うと、 913 = 11·83 が、 10 ⁸未満の合成数で合同式（3 ）が成り立つ唯一の数となる（^{[1]の 1409 ページと表 6 を参照）。 さらに詳しく計算すると、この}D、P、Q を選ぶ方法では、 10 ¹⁵未満の奇数の合成数で合同式（ 3 ）が成り立つものは5 つしかないことがわかる。^[7]${\displaystyle \left({\tfrac {D}{n}}\right)}$

の場合、追加の計算をほとんど必要としないさらなる合同条件を実装できます。 ${\displaystyle Q\neq \pm 1}$

は の計算中に計算されることを思い出してください。また、以前に計算した の累乗、つまりを簡単に保存できます。 ${\displaystyle Q^{n+1}}$${\displaystyle U_{n+1}}$${\displaystyle Q}$${\displaystyle Q^{(n+1)/2}}$

nが素数の場合、オイラーの基準により、

${\displaystyle Q^{(n-1)/2}\equiv \left({\tfrac {Q}{n}}\right){\pmod {n}}}$。

(ここで、はルジャンドル記号です。nが素数の場合、これはヤコビ記号と同じです)。 ${\displaystyle \left({\tfrac {Q}{n}}\right)}$

したがって、nが素数であれば、

右側のヤコビ記号は計算が簡単なので、この合同性は簡単に確認できます。この合同性が成り立たない場合、nは素数ではありません。GCD( n,Q )=1の場合、合同性( 4 )のテストは、Lucasテストに「基数Q」のSolovay-Strassen素数性テストを追加することと同じです。

nが素数である場合に満たさなければならない追加の合同条件は、 ^[1]の第6節で説明されています。これらの条件のいずれかが満たされない場合は、 nが素数ではないことが証明されます。

ミラー・ラビン素数判定をk 回適用すると、合成数nがおそらく素数である確率は最大で (1/4) ^kになります。

強いルーカス素数検定でも同様の確率推定値がある。^[8]

2 つの些細な例外 (以下を参照) を除けば、合成数n がおそらく素数であると宣言する( P、Q ) ペア ( nを法として)の割合は、最大で (4/15) です。

したがって、強いルーカステストをk 回適用すると、合成数n がおそらく素数である確率は最大で (4/15) ^kになります。

2 つの簡単な例外があります。1 つはn = 9 です。もう 1 つはn = p ( p +2) が 2 つの双子素数の積である場合です。このようなn は因数分解が簡単です。この場合、n +1 = ( p +1) ^{2 は完全な平方数だからです。}ニュートン法の平方根 法を使用すると、完全な平方数をすばやく検出できます。

ルーカス擬素数テストとフェルマー素数判定テスト（例えば、2を底とする）を組み合わせることで、ベイリー-PSW素数判定テストのような素数判定の非常に強力な確率的テストを得ることができます。

P = 1 かつQ = −1の場合、U _n ( P , Q ) シーケンスはフィボナッチ数列を表します。

フィボナッチ擬素数は、多くの場合^{[2] : 264、   [3] : 142、   [4] : 127}のように、 5 で割り切れない 合成数nで、 P = 1 かつQ = −1 のときに合同 ( 1 ) が成り立つものとして定義されます。この定義によれば、フィボナッチ擬素数は次の数列を形成します。

323、377、1891、3827、4181、5777、6601、6721、8149、10877、...（OEISの配列A081264）。

以下のアンダーソンとヤコブセンの参考文献ではこの定義が使用されています。

nが5を法として2または3と合同である場合、Bressoud ^{[2] :272–273}およびCrandallとPomerance ^{[3] :143,168は、}フィボナッチ擬素数が底2のフェルマー擬素数でもあることはまれであると指摘しています。しかし、nが5を法として1または4と合同である場合は逆のことが当てはまり、1011未満のフィボナッチ擬素数の12%以上が^底2のフェルマー擬素数でもあります。

nが素数でGCD( n , Q )=1のとき、 ^[1]も成り立つ^:1392

これにより、フィボナッチ擬素数の別の定義が導かれる: ^{[9] [10]}

フィボナッチ擬素数とは、 P = 1かつQ = −1のときに合同( 5 )が成り立つ合成数nである。

この定義により、フィボナッチ擬素数は次の数列を形成します。

705、2465、2737、3745、4181、5777、6721、10877、13201、15251、...（OEISの配列A005845）、

これらはブルックマン・ルーカス擬素数とも呼ばれる。^{[4] : 129} ホガットとビックネルは1974年にこれらの擬素数の特性を研究した。^[11]シングマスターはこれらの擬素数を100000まで計算した。^{[12]ヤコブセンは1013}未満のこれらの擬素数111443個すべてをリストアップしている。^[13]

式(5)で定義される偶数フィボナッチ擬素数は存在しないことが示されている。^{[14] [15]}しかし、式( 1 )で与えられた最初の定義の下では偶数フィボナッチ擬素数は存在する（ OEISのシーケンスA141137 ） 。

強いフィボナッチ擬素数とは、 Q = −1 かつすべてのPに対して合同 ( 5 ) が成り立つよう^な合成数nのことである。^{[ 16]}奇数の合成整数nが強いフィボナッチ擬素数となるのは、次の場合のみである 。

1. nはカーマイケル数である
2. n を割り切るすべての素数pに対して、 2( p + 1) | ( n − 1) または 2( p + 1) | ( n − p ) となります。

強いフィボナッチ擬素数の最小の例は 443372888629441 = 17·31·41·43·89·97·167·331 です。

ペル擬素数は、 P = 2かつQ = −1のときに上記式( 1 )が成り立つ合成数nとして定義される。この場合、数列U _nはペル数列となる。最初の擬素数は35、169、385、779、899、961、1121、1189、2419、...である。

これは、次のように記述される OEIS : A099011の定義とは異なります。

${\displaystyle {\text{ }}U_{n}\equiv \left({\tfrac {2}{n}}\right){\pmod {n}}}$

( P , Q ) = (2, −1)で、 U _{n を}再びペル数列として定義します。最初の擬素数は 169、385、741、961、1121、2001、3827、4879、5719、6215 ... です。

3番目の定義では、式(5)で( P , Q )=(2,−1)とし、擬素数169、385、961、1105、1121、3827、4901、6265、6441、6601、7107、7801、8119、...を得る。

• アンダーソン、ピーター G. フィボナッチ擬素数、その因数、およびそのエントリ ポイント。
• アンダーソン、ピーター G. 2,217,967,487 未満のフィボナッチ擬素数とその因数。
• Jacobsen、Dana 擬素数の統計、表、およびデータ (10 ^{14未満の Lucas、Strong Lucas、AES Lucas、ES Lucas 擬素数、10 12}未満のフィボナッチおよびペル擬素数のデータ)
• Weisstein、Eric W.「フィボナッチ擬素数」。MathWorld。
• Weisstein、Eric W.「ルーカス擬素数」。MathWorld。
• Weisstein、Eric W.「強いルーカス擬素数」。MathWorld。
• Weisstein、Eric W.「超強力ルーカス擬素数」。MathWorld。