リュカ擬素数のソースを表示

'''リュカ擬素数'''(en:Lucas_pseudoprime)は、任意の[[素数]]と非常に少数の[[合成数]]が通過する特定のテストに合格する合成数である。

== 関連項目 ==

* [[フィボナッチ擬素数]]

== ベイリー・ワグスタッフ・リュカ擬素数 ==
ベイリーとワグスタッフは、リュカ擬素数を次のように定義している。

自然数''P''と整数''Q''に対して、<math display="inline">D=P^2-4Q</math> とおき、<math display="inline">U_k(P,Q),V_k(P,Q)</math> をそれぞれ対応する[[:en:Lucas_sequence|リュカ数列]]とする。

自然数''n''に対して、''<math display="inline">\left ( \frac{D}{n} \right )</math>''を[[ルジャンドル記号]]とする。また、<math display="inline">\delta(n)=n-\left ( \frac{D}{n} \right )</math>とおく。

もし、''n''が<math display="inline">\gcd(n,Q)=1</math> なる素数である場合、次式が成り立つ。この式を(1)とする。

<math display="block">U_{\delta(n)}\equiv 0 \mod n </math>

式(1)が成り立たないならば、''n''は素数でない。''n''が合成数ならば、式(1)は一般的には成り立たない。これらのことは、リュカ数列を[[:en:Primality_test|素数性テスト]]で有用にする重要な事実である。

== リュカ確率的素数と擬素数 ==
与えられた組(''P'',''Q'')に対して、'''リュカ確率的素数'''とは、式(1)を満たすような任意の自然数''n''のことである。

与えられた組(''P'',''Q'')に対して、'''リュカ擬素数'''とは、式(1)を満たすような正の合成数''n''のことである。

リュカテストはルジャンドル記号<math display="inline">\left ( \frac{D}{n} \right ) </math>が<math display="inline">-1</math>になるように''D''が選択されているときに最も有用である。これは、リュカテストを[[:en:Baillie-PSW_primality_test|Baillie-PSW素数テスト]]などの強力な擬素数テストと組み合わせる場合に特に重要である。

通常、実用的には、この条件を確実にするパラメーター選択方法を用いる。例えばセルフリッジ方式などである。

もし、<math display="inline">\left ( \frac{D}{n} \right )=-1 </math>ならば、式(1)は次のようになる。

<math display="block">U_{n+1}\equiv 0 \mod n. </math>

この式を(2)とおく。式(2)が成り立たない場合、これはnが合成数であることを示している。式(2)が成り立っている場合、''n''はリュカ確率的素数である。このとき、''n''は素数であるか、リュカ擬素数である。

式(2)が真の場合、''n''は素数になる可能性がある(これにより、確率的素数が正当化される)が、これは''n''が素数であることを示しているわけではないことに注意されたい。他の確率的素数テストと同様に、異なる''D'',''P'',''Q''に対して更にリュカテストを実行するとき、いずれかのテストで''n''が合成数であることが証明されない限り、''n''が素数である可能性が高まる。

=== 例1 ===
<math display="inline">P=3, Q=-1, D=13</math> の場合、''U''の数列は[[:en:On-Line_Encyclopedia_of_Integer_Sequences|OEIS]]: [[oeis:A006190|A006190]]:<math display="inline">U_0=0,U_1=1, U_2=3,...</math>である。

まず、''n''=19とする。ルジャンドル記号は<math display="block">\left ( \frac{13}{19} \right )=-1</math>であるから、<math display="inline">\delta(n)=20</math>,

<math display="block">U_{20}=6616217487\equiv 0 \mod 19.</math>である。従って、19はこの組(''P'',''Q'')=(3,-1)に対するリュカ確率的素数である。この場合、19は素数なので、リュカ擬素数ではない。

=== 例2 ===
''P'',''Q'',''D''は例1と同様とし、''n''=119とする。 <math display="inline">\left ( \frac{13}{19} \right )=-1</math>であり、

<math display="block">U_{120}\equiv 0 \mod 119.</math>

と計算される。しかしながら、<math display="inline">119=7 \cdot 17</math>は素数でない。よって119はこの組(''P'',''Q'')=(3,-1)に対するリュカ擬素数である。実際、119は組(''P'',''Q'')=(3,-1)に対する最小のリュカ擬素数である。

以下で、与えられた''n''について式(2)を調べるために、数列''U''の最初の''n''+1項を全て計算する必要はない。

=== 例3 ===
''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, ...

である。

== 強いリュカ擬素数 ==
ここで、<math display="inline">\delta(n)=n-\left ( \frac{D}{n} \right )</math>を''d''が奇数であるような、数 <math display="inline">d\cdot 2^s</math>に分解する。

与えられた組(''P'',''Q'')に対して、'''強いリュカ擬素数'''は、<math display="inline">\gcd(n,D)=1</math> なる奇数の合成数''n''であり、ある <math display="inline">0\leq r < s</math> に対して、条件

<math display="block">U_d\equiv 0 \mod n</math>

または、

<math display="block">V_{d\cdot 2^r}\equiv 0 \mod n</math>のいずれかを満たす。強いリュカ擬素数は同じ組(''P'',''Q'')に対するリュカ擬素数でもあるが、逆は必ずしも成立しない。従って、'''強い'''テストは式(1)よりも厳密な素数性判定法である。

''Q''=-1とすると、<math display="inline">U_n</math>と <math display="inline">V_n</math>は''P''-フィボナッチ数列と''P''-リュカ数列である。擬素数は'''''P''を底として強い擬素数'''と呼ぶことも可能である。例えば、''P''=1,2,3,...に対する最小の強いリュカ擬素数は、4181,169,119,...である。

'''非常に強いリュカ擬素数'''は、パラメーター(''P'',''Q'')(''Q''=-1)の集合に対する強いリュカ擬素数で、ある <math display="inline">0\leq r < s-1</math> に対して、条件

<math display="block">U_d\equiv 0 \mod n,\text{and}~ V_d \equiv\pm 2 \mod n </math>

または、

<math display="block">V_{d\cdot 2^r}\equiv 0 \mod n</math><br />のいずれかを満たす。

非常に強いリュカ擬素数はまた、同じ組(''P'',''Q'')に対する強いリュカ擬素数でもある。

== リュカ確率的素数テストの実装 ==
確率的素数テストに着手する前に、通常、素数性を判定する数である''n''が奇数であり、完全平方ではなく、更にある便利な制限よりも小さい任意の素数で割り切れないことを確認する。完全平方は平方根に対する[[ニュートン法]]を用いて簡単に判定できる。

ルジャンドル記号<math display="inline">\left ( \frac{D}{n} \right )=-1</math> 即ち、<math display="inline">\delta(n)=n+1</math>なるリュカ数列を選ぶ。

与えられた''n''に対して、''Dを選ぶ一つの手法は、試行錯誤で、''<math display="inline">\left ( \frac{D}{n} \right )=-1</math>なる数列5,-7,9,-11,...の最初の''D''を見つけることである。<math display="inline">\left ( \frac{k}{n} \right )\left ( \frac{-k}{n} \right )=-1</math>であることに注意されたい。もし、''D''と''n''が共通の素因子をもつならば、<math display="inline">\left ( \frac{D}{n} \right )=0</math>である。この''D''値の数列では、ルジャンドル記号が-1である''D値に出会う前に試行する必要があるD値の平均数は''1.79''である。１度Dを得ると、''

<math display="inline">P=1, Q=\frac{1-D}{4}</math>とする。''n''に''P''または''Q''と共通の素因子がないことを確認せよ。''D'',''P'',''Q''を選択するこの方法は、[[:en:John_Selfridge|ジョンセルフリッジ]]によって提案された。

(''n''が平方の場合、このテストは成功しない。逆に、成功した場合、''n''が平方でないことを示しています。従って、最初の数回の検索段階が全て失敗するまで、平方性に対する''n''のテストを遅らせることで、時間を節約することができる。)

与えられた''D'',''P'',''Qに対して、''<math display="inline">O(\log_2 n)</math>で <math display="inline">U_{n+1}</math> 及び <math display="inline">V_{n+1}</math> を素早く計算する漸化式がある([[:en:Lucas_sequence#Other_relations|Lucas sequence § Other relations]]を参照せよ)。

まず、

<math display="block">U_1=1, V_1=P=1</math>

であり、漸化式を用いて、添え字を''k''から2''k''に2倍すると、

<math display="block">U_{2k}=U_k\cdot V_k</math><math display="block">V_{2k}=V_k^2-2Q^k=\frac{V_k^2+DU_k^2}{2}.</math>

次に、反復を用いて添え字を1ずつ増やすと、

<math display="block">U_{2k+1}=\dfrac{P\cdot U_{2k}+V_{2k}}{2}</math><math display="block">V_{2k+1}=\frac{D\cdot U_{2k}+P\cdot V_{2k}}{2}.</math>

<math display="inline">P\cdot U_{2k}+V_{2k}</math> が奇数の場合は、これを

<math display="block">P\cdot U_{2k}+V_{2k}+n</math>で置き換える。これは偶数であるから2で割ることができる。

<math display="inline">V_{2k+1}</math>の分子も同様の方法で処理する(''n''を足しても、''n''を法とする結果は変わらない)。数列''Uで計算する各記号について、数列Vで対応する記号を計算することに注意されたい。次の段階で、対応する同じQの冪乗も計算する。''

各段階で、<math display="inline">U,V</math> 及び <math display="inline">Q</math> の冪を<math display="inline">\mod n</math>で計算し、小さくしておく。

''nの2進展開のビットを用いて、計算する数列Uの項を決定する。例えば、n''+1=44(=101100,2進数)のとき、左から右に1度に1つずつビットを取って、計算する添え字の数列を得る。

<math display="block">1_2=1,10_2=2,100_2=4,101_2=5,1010_2=10,1011_2=11,10110_2=22,101100_2=44</math>

従って、<math display="inline">U_1,U_2,U_4,U_5,U_{10},U_{11},U_{22},U_{44}</math>を計算すればよい。また、

<math display="inline">Q_1,Q_2,Q_4,Q_5,Q_{10},Q_{11},Q_{22},Q_{44}</math>と共に、数列''V内の同じ番号の項を計算する。''

''計算の終わりまでに、''<math display="inline">U_{n+1},V_{n+1},Q_{n+1} \mod n</math>を計算し、既知の <math display="inline">U_{n+1}</math> の値を用いて、式(2)の合同性を確かめる。

上記のように''D'',''P'',''Q''を選択すると、最初の10個のリュカ擬素数は、323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, 10877([[:en:On-Line_Encyclopedia_of_Integer_Sequences|OEIS]]:[[oeis:A217120|A217120]])である。

'''強い'''リュカテストも同様の方法で実装できる。

上記のように''D'',''P'',''Q''を選択すると、最初の10個の強いリュカ擬素数は、5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519(OEIS:[[oeis:A217255|A217255]])である。

非常に強いリュカ擬素数のリストを計算するために、''Q''=1とおく。このとき、<math display="inline">D=P^2-4Q</math> の値が見つかるまで ''P''=3,4,5,6,...を試し、ルジャンドル記号<math display="inline">\left ( \frac{D}{n} \right )=-1</math>''を求める。この方法で、D'',''P'',''Qを選択した場合、最初の''10''個の非常に強いリュカ擬素数は、''989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389(OEIS:[[oeis:A217255|A217719]])である。
[[Category:擬素数]]
[[Category:数列]]
[[Category:数学に関する記事]]
{{DEFAULTSORT:りゆかきそすう}}