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

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

アルゴリズム

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

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

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

で定める。このとき、N = k ⋅ 2ⁿ − 1 が素数である必要十分条件は N が u_{n − 2} を割り切ることである。

初期値 u₀ の決定

初期値 u₀ は以下のように決定される。

もし k = 1 であり、さらに n ≡ 3 (mod 4) であるなら、u₀ = 3 ととる。また n ≡ 1 (mod 4) であるなら、u₀ = 4 ととる。なお、n が素数であるとき、N はメルセンヌ数になりうる。

もし k = 3 であり、かつ n ≡ 0 (mod 4) であるか n ≡ 3 (mod 4) であるなら、u₀ = 5778 ととる。なお、n ≡ 1 (mod 4) のとき N は 5 で割り切れることが容易に示される。

もし k ≡ ±1 (mod 6) であり、N が 3 で割り切れないなら、u₀ = (2 + √3)^k + (2 − √3)^k ととる。あるいは同じことだが、

$v_{n}={\begin{cases}2&{\text{if }}n=0\\4&{\text{if }}n=1\\4v_{n-1}-v_{n-2}&{\text{if }}n\geq 2\end{cases}}$

により定まる数列 {v_n} を用いて u₀ = v_k ととる。

上記以外の場合、すなわち k が 3 の倍数の場合は初期値 u₀ を決定するのはより難しくなる。

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

$\left({\frac {P-2}{N}}\right)=1,\qquad \left({\frac {P+2}{N}}\right)=-1.$

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

判定法の仕組み

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

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

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

LLR ソフトウェア

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

参考文献

• Brillhart, John; Lehmer, Derrick Henry; Selfridge, John (April 1975). “New Primality Criteria and Factorizations of 2^m ± 1”. Mathematics of Computation 29 (130): 620 – 647. doi:10.1090/S0025-5718-1975-0384673-1. 
• Riesel, Hans (1969). “Lucasian Criteria for the Primality of N = h⋅ 2ⁿ − 1”. Mathematics of Computation (American Mathematical Society) 23 (108): 869 – 875. doi:10.2307/2004975. JSTOR 2004975. 
• Riesel, Hans (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (2nd ed.). Birkhauser. pp. 107 – 121. ISBN 0-8176-3743-5 
• Rodseth, Oystein J. (1994). “A note on primality tests for N = h⋅ 2ⁿ − 1”. BIT Numerical Mathematics 34 (3): 451 – 454. doi:10.1007/BF01935653. オリジナルのMarch 6, 2016時点におけるアーカイブ。. https://web.archive.org/web/20160306082833/http://folk.uib.no/nmaoy/papers/luc.pdf. 

関連項目

• リーゼル数

外部リンク

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