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

リュカ–レーマー–リーゼル・テスト（、またはLLRテスト）とは、数学の特に数論において、（ただし は を満たす奇数）という形の正整数に対する素数判定法である。この判定法はリュカ–レーマー・テストに基づいてハンス・リーゼルにより開発された。第2項の符号が異なる （プロス数）に対しては、に基づくラスベガス法や Brillhart–Lehmer–Selfridgeの結果に基づく決定的アルゴリズムが用いられる。
アルゴリズム.
この判定法のアルゴリズムはリュカ–レーマー・テストに非常によく似ているが、用いる数列 の初期値 が によって異なる。
数列 を以下で定義する。初期値 は次節のように定め、非負整数 に対して漸化式を
で定める。このとき、 が素数である必要十分条件は が を割り切ることである。
初期値 の決定.
初期値 は以下のように決定される。
により定まる数列 を用いて ととる。
初期値 を決定する別の方法が Rodseth により提示されている。 が の倍数の場合、この方法はリーゼルが用いた方法よりも簡明である。まず、以下のヤコビ記号についての方程式の解 を求める：
 の値から初期値 を見出すには、リーゼルや Rodseth が示すようにリュカ数列を用いる。なおリーゼルは が で割り切れないときは ととることができ、したがって上掲の方程式を解く必要がないことを示している。初期値 はリュカ数列 を用いて ととる。この手続きに要する時間はリュカ–レーマー–リーゼル・テスト本体と比較して少なく済む。
判定法の仕組み.
リュカ–レーマー–リーゼル・テストは群論的素数判定法の一種である。すなわち、ある数 が素数であることを、群の位数が であり、その群の元の位数も となるような群を見出すことにより示す。 
整数 に対するリュカ・テストに対しては、 を法とする2次拡大の乗法群が適用できる。すなわち、もし が素数であるなら、その乗法群の位数は であり、これは位数 の部分群を持つので、その部分群の生成元を見出せばよい。
さて、数列 のを求める。リュカ–レーマー・テストに従い、 と置くと、帰納法によって数列 が満たすべき漸化式 が成り立つことが示される。続いて、数列 の 番目の値について考えると、これはリュカ数列であって、 はある二次方程式の根となり、さらに という形の漸化式を満たす。実のところ、考慮すべきは 番目の値であるが、リュカ数列の 番目ごとの値からなる部分列は再びリュカ数列になるため、係数 を扱うためには異なる初期値を選択すればよい。
LLR ソフトウェア.
LLR はリュカ–レーマー–リーゼル・テストを実行可能なソフトウェアである。プログラムは Jean Penné により開発された。このソフトウェアは個人的に素数を探索する人々や Riesel Sieve・PrimeGrid といった分散コンピューティングプロジェクトに利用されている。