リュカ擬素数

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

1. 関連項目
-------

フィボナッチ擬素数

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

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

自然数//P//と整数//Q//に対して、 とおき、 をそれぞれ対応するリュカ数列とする。

自然数//n//に対して、////をルジャンドル記号とする。また、とおく。

もし、//n//が なる素数である場合、次式が成り立つ。この式をとする。

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

3. リュカ確率的素数と擬素数
---------------

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

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

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

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

もし、ならば、式は次のようになる。

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

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

3.1. 例1
-------

の場合、//U//の数列はOEIS: A006190:である。

まず、//n//=19とする。ルジャンドル記号はであるから、,

である。従って、19はこの組=に対するリュカ確率的素数である。この場合、19は素数なので、リュカ擬素数ではない。

3.2. 例2
-------

//P//,//Q//,//D//は例1と同様とし、//n//=119とする。 であり、

と計算される。しかしながら、は素数でない。よって119はこの組=に対するリュカ擬素数である。実際、119は組=に対する最小のリュカ擬素数である。

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

3.3. 例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, ...

である。

4. 強いリュカ擬素数
-----------

ここで、を//d//が奇数であるような、数 に分解する。

与えられた組に対して、強いリュカ擬素数は、 なる奇数の合成数//n//であり、ある に対して、条件

または、

のいずれかを満たす。強いリュカ擬素数は同じ組に対するリュカ擬素数でもあるが、逆は必ずしも成立しない。従って、強いテストは式よりも厳密な素数性判定法である。

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

非常に強いリュカ擬素数は、パラメーターの集合に対する強いリュカ擬素数で、ある に対して、条件

または、

のいずれかを満たす。

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

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

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

ルジャンドル記号 即ち、なるリュカ数列を選ぶ。

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

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



与えられた//D//,//P//,//Qに対して、//で 及び を素早く計算する漸化式がある。

まず、

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

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

が奇数の場合は、これを

で置き換える。これは偶数であるから2で割ることができる。

の分子も同様の方法で処理する。数列//Uで計算する各記号について、数列Vで対応する記号を計算することに注意されたい。次の段階で、対応する同じQの冪乗も計算する。//

各段階で、 及び の冪をで計算し、小さくしておく。

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

従って、を計算すればよい。また、

と共に、数列//V内の同じ番号の項を計算する。//

//計算の終わりまでに、//を計算し、既知の の値を用いて、式の合同性を確かめる。

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

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

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

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