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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/01 04:02 UTC 版)

数学の特に数論において、リュカ–レーマー–リーゼル・テスト（英: Lucas–Lehmer–Riesel test）またはLLRテスト（エルエルアールテスト）とは、 N = k ⋅ 2ⁿ − 1（ただし k は k < 2ⁿ を満たす奇数）という形の正整数 N に対する素数判定法である。

この判定法はリュカ–レーマー・テストに基づいて、スウェーデンの数学者ハンス・リーゼルにより開発された。

第2項の符号が異なる N′ = k ⋅ 2ⁿ + 1（プロス数）に対しては、プロスの定理に基づくラスベガス法や Brillhart–Lehmer–Selfridgeの結果に基づく決定的アルゴリズムが用いられる。

アルゴリズム

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

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

$u_{i+1}=u_{i}^{2}-2$