リュカ–レーマー–リーゼル・テスト

リュカ–レーマー–リーゼル・テスト（、またはLLRテスト）とは、数学の特に数論において、（ただし  は  を満たす奇数）という形の正整数に対する素数判定法である。この判定法はリュカ–レーマー・テストに基づいてハンス・リーゼルにより開発された。第2項の符号が異なる （プロス数）に対しては、に基づくラスベガス法や Brillhart–Lehmer–Selfridgeの結果に基づく決定的アルゴリズムが用いられる。

アルゴリズム 
この判定法のアルゴリズムはリュカ–レーマー・テストに非常によく似ているが、用いる数列  の初期値  が  によって異なる。

数列  を以下で定義する。初期値  は次節のように定め、非負整数  に対して漸化式を

で定める。このとき、 が素数である必要十分条件は  が  を割り切ることである。

初期値  の決定 
初期値  は以下のように決定される。
 もし  であり、さらに  であるなら、 ととる。また  であるなら、 ととる。なお、 が素数であるとき、 はメルセンヌ数になりうる。
 もし  であり、かつ  であるか  であるなら、 ととる。なお、 のとき  は  で割り切れることが容易に示される。
 もし  であり、 が  で割り切れないなら、 ととる。あるいは同じことだが、
 
により定まる数列  を用いて  ととる。
 上記以外の場合、すなわち  が  の倍数の場合は初期値  を決定するのはより難しくなる。

初期値  を決定する別の方法が Rodseth により提示されている。 が  の倍数の場合、この方法はリーゼルが用いた方法よりも簡明である。まず、以下のヤコビ記号についての方程式の解  を求める：

 

 の値から初期値  を見出すには、リーゼルや Rodseth が示すようにリュカ数列を用いる。なおリーゼルは  が  で割り切れないときは  ととることができ、したがって上掲の方程式を解く必要がないことを示している。初期値  はリュカ数列  を用いて  ととる。この手続きに要する時間はリュカ–レーマー–リーゼル・テスト本体と比較して少なく済む。

判定法の仕組み 
リュカ–レーマー–リーゼル・テストは群論的素数判定法の一種である。すなわち、ある数  が素数であることを、群の位数が  であり、その群の元の位数も  となるような群を見出すことにより示す。 

整数  に対するリュカ・テストに対しては、 を法とする2次拡大の乗法群が適用できる。すなわち、もし  が素数であるなら、その乗法群の位数は  であり、これは位数 の部分群を持つので、その部分群の生成元を見出せばよい。

さて、数列  のを求める。リュカ–レーマー・テストに従い、 と置くと、帰納法によって数列  が満たすべき漸化式  が成り立つことが示される。続いて、数列  の  番目の値について考えると、これはリュカ数列であって、 はある二次方程式の根となり、さらに  という形の漸化式を満たす。実のところ、考慮すべきは  番目の値であるが、リュカ数列の  番目ごとの値からなる部分列は再びリュカ数列になるため、係数  を扱うためには異なる初期値を選択すればよい。

LLR ソフトウェア 
LLR はリュカ–レーマー–リーゼル・テストを実行可能なソフトウェアである。プログラムは Jean Penné により開発された。このソフトウェアは個人的に素数を探索する人々や Riesel Sieve・PrimeGrid といった分散コンピューティングプロジェクトに利用されている。

脚注

参考文献

関連項目 
 リーゼル数

外部リンク 
Download Jean Penné's LLR
Math::Prime::Util::GMP - Perl の ntheory モジュールの一部であり、LLR の基本的な実装とプロス数に対する Brillhart–Lehmer–Selfridge テストと同様のものが実装されている。

数学に関する記事
素数判定