リュカ擬素数

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

## 関連項目

* フィボナッチ擬素数

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

自然数*P*と整数*Q*に対して、D=P^2-4Q とおき、U_k(P,Q),V_k(P,Q) をそれぞれ対応するリュカ数列とする。

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

もし、*n*が\gcd(n,Q)=1 なる素数である場合、次式が成り立つ。この式を(1)とする。

U_{\delta(n)}\equiv 0 \mod n 

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

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

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

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

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

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

U_{n+1}\equiv 0 \mod n. 

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

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

### 例1
P=3, Q=-1, D=13 の場合、*U*の数列はOEIS: :U_0=0,U_1=1, U_2=3,...である。

まず、*n*=19とする。ルジャンドル記号は\left ( \frac{13}{19} \right )=-1であるから、\delta(n)=20,

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

### 例2
*P*,*Q*,*D*は例1と同様とし、*n*=119とする。 \left ( \frac{13}{19} \right )=-1であり、

U_{120}\equiv 0 \mod 119.

と計算される。しかしながら、119=7 \cdot 17は素数でない。よって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, ...

である。

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

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

U_d\equiv 0 \mod n

または、

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

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

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

U_d\equiv 0 \mod n,\text{and}~ V_d \equiv\pm 2 \mod n 

または、

V_{d\cdot 2^r}\equiv 0 \mod nのいずれかを満たす。

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

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

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

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

P=1, Q=\frac{1-D}{4}とする。*n*に*P*または*Q*と共通の素因子がないことを確認せよ。*D*,*P*,*Q*を選択するこの方法は、ジョンセルフリッジによって提案された。

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

与えられた*D*,*P*,*Qに対して、*O(\log_2 n)で U_{n+1} 及び V_{n+1} を素早く計算する漸化式がある(Lucas sequence § Other relationsを参照せよ)。

まず、

U_1=1, V_1=P=1

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

U_{2k}=U_k\cdot V_kV_{2k}=V_k^2-2Q^k=\frac{V_k^2+DU_k^2}{2}.

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

U_{2k+1}=\dfrac{P\cdot U_{2k}+V_{2k}}{2}V_{2k+1}=\frac{D\cdot U_{2k}+P\cdot V_{2k}}{2}.

P\cdot U_{2k}+V_{2k} が奇数の場合は、これを

P\cdot U_{2k}+V_{2k}+nで置き換える。これは偶数であるから2で割ることができる。

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

各段階で、U,V 及び Q の冪を\mod nで計算し、小さくしておく。

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

1_2=1,10_2=2,100_2=4,101_2=5,1010_2=10,1011_2=11,10110_2=22,101100_2=44

従って、U_1,U_2,U_4,U_5,U_{10},U_{11},U_{22},U_{44}を計算すればよい。また、

Q_1,Q_2,Q_4,Q_5,Q_{10},Q_{11},Q_{22},Q_{44}と共に、数列*V内の同じ番号の項を計算する。*

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

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

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

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

非常に強いリュカ擬素数のリストを計算するために、*Q*=1とおく。このとき、D=P^2-4Q の値が見つかるまで *P*=3,4,5,6,...を試し、ルジャンドル記号\left ( \frac{D}{n} \right )=-1*を求める。この方法で、D*,*P*,*Qを選択した場合、最初の*10*個の非常に強いリュカ擬素数は、*989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389(OEIS:)である。