リュカ擬素数

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

関連項目

  • フィボナッチ擬素数

ベイリー・ワグスタッフ・リュカ擬素数

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

自然数Pと整数Qに対して、 D = P 2 − 4 Q {\textstyle D=P^{2}-4Q} とおき、 U k ( P , Q ) , V k ( P , Q ) {\textstyle U_{k}(P,Q),V_{k}(P,Q)} をそれぞれ対応するリュカ数列とする。

自然数nに対して、 ( D n ) {\textstyle \left({\frac {D}{n}}\right)} をルジャンドル記号とする。また、 δ ( n ) = n − ( D n ) {\textstyle \delta (n)=n-\left({\frac {D}{n}}\right)} とおく。

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

U δ ( n ) ≡ 0 mod n {\displaystyle U_{\delta (n)}\equiv 0\mod n}

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

リュカ確率的素数と擬素数

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

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

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

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

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

U n + 1 ≡ 0 mod n . {\displaystyle 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 {\textstyle P=3,Q=-1,D=13} の場合、Uの数列はOEIS: A006190: U 0 = 0 , U 1 = 1 , U 2 = 3 , . . . {\textstyle U_{0}=0,U_{1}=1,U_{2}=3,...} である。

まず、n=19とする。ルジャンドル記号は

( 13 19 ) = − 1 {\displaystyle \left({\frac {13}{19}}\right)=-1}
であるから、 δ ( n ) = 20 {\textstyle \delta (n)=20} ,

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

例2

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

U 120 ≡ 0 mod 119. {\displaystyle U_{120}\equiv 0\mod 119.}

と計算される。しかしながら、 119 = 7 ⋅ 17 {\textstyle 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, ...

である。

強いリュカ擬素数

ここで、 δ ( n ) = n − ( D n ) {\textstyle \delta (n)=n-\left({\frac {D}{n}}\right)} をdが奇数であるような、数 d ⋅ 2 s {\textstyle d\cdot 2^{s}} に分解する。

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

U d ≡ 0 mod n {\displaystyle U_{d}\equiv 0\mod n}

または、

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

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

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

U d ≡ 0 mod n , and   V d ≡ ± 2 mod n {\displaystyle U_{d}\equiv 0\mod n,{\text{and}}~V_{d}\equiv \pm 2\mod n}

または、

V d ⋅ 2 r ≡ 0 mod n {\displaystyle V_{d\cdot 2^{r}}\equiv 0\mod n}

のいずれかを満たす。

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

リュカ確率的素数テストの実装

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

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

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

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

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

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

まず、

U 1 = 1 , V 1 = P = 1 {\displaystyle U_{1}=1,V_{1}=P=1}

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

U 2 k = U k ⋅ V k {\displaystyle U_{2k}=U_{k}\cdot V_{k}}
V 2 k = V k 2 − 2 Q k = V k 2 + D U k 2 2 . {\displaystyle V_{2k}=V_{k}^{2}-2Q^{k}={\frac {V_{k}^{2}+DU_{k}^{2}}{2}}.}

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

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

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

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

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

各段階で、 U , V {\textstyle U,V} 及び Q {\textstyle Q} の冪を mod n {\textstyle \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 {\displaystyle 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 {\textstyle 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 {\textstyle 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 {\textstyle U_{n+1},V_{n+1},Q_{n+1}\mod n} を計算し、既知の U n + 1 {\textstyle U_{n+1}} の値を用いて、式(2)の合同性を確かめる。

上記のようにD,P,Qを選択すると、最初の10個のリュカ擬素数は、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)である。

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