数学の特に数論において、リュカ–レーマー–リーゼル・テスト（）または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 テストと同様のものが実装されている。