リュカ擬素数

リュカ擬素数(en:Lucas_pseudoprime)は、任意の素数と非常に少数の合成数が通過する特定のテストに合格する合成数である。
ベイリー・ワグスタッフ・リュカ擬素数.
ベイリーとワグスタッフは、リュカ擬素数を次のように定義している。
自然数"P"と整数"Q"に対して、formula_1 とおき、formula_2 をそれぞれ対応するとする。
自然数"n"に対して、"formula_3"をルジャンドル記号とする。また、formula_4とおく。
もし、"n"がformula_5 なる素数である場合、次式が成り立つ。この式を(1)とする。
formula_6
式(1)が成り立たないならば、"n"は素数でない。"n"が合成数ならば、式(1)は一般的には成り立たない。これらのことは、リュカ数列をで有用にする重要な事実である。
リュカ確率的素数と擬素数.
与えられた組("P","Q")に対して、リュカ確率的素数とは、式(1)を満たすような任意の自然数"n"のことである。
与えられた組("P","Q")に対して、リュカ擬素数とは、式(1)を満たすような正の合成数"n"のことである。
リュカテストはルジャンドル記号formula_7がformula_8になるように"D"が選択されているときに最も有用である。これは、リュカテストをなどの強力な擬素数テストと組み合わせる場合に特に重要である。
通常、実用的には、この条件を確実にするパラメーター選択方法を用いる。例えばセルフリッジ方式などである。
もし、formula_9ならば、式(1)は次のようになる。
formula_10
この式を(2)とおく。式(2)が成り立たない場合、これはnが合成数であることを示している。式(2)が成り立っている場合、"n"はリュカ確率的素数である。このとき、"n"は素数であるか、リュカ擬素数である。
式(2)が真の場合、"n"は素数になる可能性がある(これにより、確率的素数が正当化される)が、これは"n"が素数であることを示しているわけではないことに注意されたい。他の確率的素数テストと同様に、異なる"D","P","Q"に対して更にリュカテストを実行するとき、いずれかのテストで"n"が合成数であることが証明されない限り、"n"が素数である可能性が高まる。
例1.
formula_11 の場合、"U"の数列は: :formula_12である。
まず、"n"=19とする。ルジャンドル記号はformula_13であるから、formula_14,
formula_15である。従って、19はこの組("P","Q")=(3,-1)に対するリュカ確率的素数である。この場合、19は素数なので、リュカ擬素数ではない。
例2.
"P","Q","D"は例1と同様とし、"n"=119とする。 formula_16であり、
formula_17
と計算される。しかしながら、formula_18は素数でない。よって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, ...
である。
強いリュカ擬素数.
ここで、formula_4を"d"が奇数であるような、数 formula_20に分解する。
与えられた組("P","Q")に対して、強いリュカ擬素数は、formula_21 なる奇数の合成数"n"であり、ある formula_22 に対して、条件
formula_23
または、
formula_24のいずれかを満たす。強いリュカ擬素数は同じ組("P","Q")に対するリュカ擬素数でもあるが、逆は必ずしも成立しない。従って、強いテストは式(1)よりも厳密な素数性判定法である。
"Q"=-1とすると、formula_25と formula_26は"P"-フィボナッチ数列と"P"-リュカ数列である。擬素数は"P"を底として強い擬素数と呼ぶことも可能である。例えば、"P"=1,2,3...に対する最小の強いリュカ擬素数は、4181,169,119...である。
非常に強いリュカ擬素数は、パラメーター("P","Q")("Q"=-1)の集合に対する強いリュカ擬素数で、ある formula_27 に対して、条件
formula_28
または、
formula_24のいずれかを満たす。
非常に強いリュカ擬素数はまた、同じ組("P","Q")に対する強いリュカ擬素数でもある。
リュカ確率的素数テストの実装.
確率的素数テストに着手する前に、通常、素数性を判定する数である"n"が奇数であり、完全平方ではなく、更にある便利な制限よりも小さい任意の素数で割り切れないことを確認する。完全平方は平方根に対するニュートン法を用いて簡単に判定できる。
ルジャンドル記号formula_30 即ち、formula_31なるリュカ数列を選ぶ。
与えられた"n"に対して、"Dを選ぶ一つの手法は、試行錯誤で、"formula_30なる数列5,-7,9,-11...の最初の"D"を見つけることである。formula_33であることに注意されたい。もし、"D"と"n"が共通の素因子をもつならば、formula_34である。この"D"値の数列では、ルジャンドル記号が-1である"D値に出会う前に試行する必要があるD値の平均数は"1.79"である。１度Dを得ると、"
formula_35とする。"n"に"P"または"Q"と共通の素因子がないことを確認せよ。"D","P","Q"を選択するこの方法は、によって提案された。
与えられた"D","P","Qに対して、"formula_36で formula_37 及び formula_38 を素早く計算する漸化式がある(を参照せよ)。
まず、
formula_39
であり、漸化式を用いて、添え字を"k"から2"k"に2倍すると、
formula_40formula_41
次に、反復を用いて添え字を1ずつ増やすと、
formula_42formula_43
formula_44 が奇数の場合は、これを
formula_45で置き換える。これは偶数であるから2で割ることができる。
formula_46の分子も同様の方法で処理する("n"を足しても、"n"を法とする結果は変わらない)。数列"Uで計算する各記号について、数列Vで対応する記号を計算することに注意されたい。次の段階で、対応する同じQの冪乗も計算する。"
各段階で、formula_47 及び formula_48 の冪をformula_49で計算し、小さくしておく。
"nの2進展開のビットを用いて、計算する数列Uの項を決定する。例えば、n"+1=44(=101100,2進数)のとき、左から右に1度に1つずつビットを取って、計算する添え字の数列を得る。
formula_50
従って、formula_51を計算すればよい。また、
formula_52と共に、数列"V内の同じ番号の項を計算する。"
"計算の終わりまでに、"formula_53を計算し、既知の formula_37 の値を用いて、式(2)の合同性を確かめる。
上記のように"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(OEIS:)である。
非常に強いリュカ擬素数のリストを計算するために、"Q"=1とおく。このとき、formula_1 の値が見つかるまで "P"=3,4,5,6...を試し、ルジャンドル記号formula_30"を求める。この方法で、D","P","Qを選択した場合、最初の"10"個の非常に強いリュカ擬素数は、"989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, 72389(OEIS:)である。