リュカ–レーマー–リーゼル・テスト
リュカ–レーマー–リーゼル・テスト(英: Lucas–Lehmer–Riesel test、またはLLRテスト)とは、数学の特に数論において、N = k ⋅ 2 − 1(ただし k は k < 2 を満たす奇数)という形の正整数に対する素数判定法である。この判定法はリュカ–レーマー・テストに基づいてハンス・リーゼルにより開発された。第2項の符号が異なる N′ = k ⋅ 2 + 1(プロス数)に対しては、プロスの定理(英語版)に基づくラスベガス法や Brillhart–Lehmer–Selfridgeの結果に基づく決定的アルゴリズムが用いられる。
この判定法のアルゴリズムはリュカ–レーマー・テストに非常によく似ているが、用いる数列 {ui} の初期値 u0 が k によって異なる。
数列 {ui} を以下で定義する。初期値 u0 は次節のように定め、非負整数 i ≥ 0 に対して漸化式を
u i + 1 = u i 2 − 2 {\displaystyle u_{i+1}=u_{i}^{2}-2}
で定める。このとき、N = k ⋅ 2 − 1 が素数である必要十分条件は N が un − 2 を割り切ることである。