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

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

アルゴリズム編集

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

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

 

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

初期値 u0 の決定編集

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

もし k = 1 であり、さらに n ≡ 3 (mod 4) であるなら、u0 = 3 ととる。また n ≡ 1 (mod 4) であるなら、u0 = 4 ととる。なお、n が素数であるとき、Nメルセンヌ数になりうる。
もし k = 3 であり、かつ n ≡ 0 (mod 4) であるか n ≡ 3 (mod 4) であるなら、u0 = 5778 ととる。なお、n ≡ 1 (mod 4) のとき N5 で割り切れることが容易に示される。
もし k ≡ ±1 (mod 6) であり、N3 で割り切れないなら、u0 = (2 + 3)k + (2 − 3)k ととる。あるいは同じことだが、
 

により定まる数列 {vn} を用いて u0 = vk ととる。

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

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

 


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

判定法の仕組み編集

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

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

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

LLR ソフトウェア編集

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

脚注編集

[脚注の使い方]

参考文献編集

  • Brillhart, John; Lehmer, Derrick Henry; Selfridge, John (April 1975). “New Primality Criteria and Factorizations of 2m ± 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⋅ 2n − 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⋅ 2n − 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. 

関連項目編集

外部リンク編集