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

数学の特に数論において、リュカ–レーマー–リーゼル・テスト（テンプレート:Lang-en-short）またはLLRテスト（エルエルアールテスト）とは、 テンプレート:Math（ただし テンプレート:Mvar は テンプレート:Math を満たす奇数）という形の正整数 テンプレート:Math に対する素数判定法である。

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

第2項の符号が異なる テンプレート:Math（プロス数）に対しては、テンプレート:仮リンクに基づくラスベガス法や Brillhart–Lehmer–Selfridgeテンプレート:Sfnの結果に基づく決定的アルゴリズムが用いられる。

アルゴリズム

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

数列 テンプレート:Mset を以下で定義する。初期値 テンプレート:Math は次節のように定め、非負整数 テンプレート:Math に対して漸化式を

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

で定める。このとき、テンプレート:Math が素数である必要十分条件は テンプレート:Mvar が テンプレート:Math を割り切ることである。

初期値 テンプレート:Math の決定

初期値 テンプレート:Math は以下のように決定される。

もし テンプレート:Math であり、さらに テンプレート:Math であるなら、テンプレート:Math ととる。また テンプレート:Math であるなら、テンプレート:Math ととる。なお、テンプレート:Mvar が素数であるとき、テンプレート:Mvar はメルセンヌ数になりうる。

もし テンプレート:Math であり、かつ テンプレート:Math であるか テンプレート:Math であるなら、テンプレート:Math ととる。なお、テンプレート:Math のとき テンプレート:Mvar は テンプレート:Mvar で割り切れることが容易に示される。

もし テンプレート:Math であり、テンプレート:Mvar が テンプレート:Mvar で割り切れないなら、テンプレート:Math ととる。あるいは同じことだが、

$v_n=\{\begin{array}{cc}2& \text{if }n=0\\ 4& \text{if }n=1\\ 4v_{n-1}-v_{n-2}& \text{if }n\ge 2\end{array}$

により定まる数列 テンプレート:Mset を用いて テンプレート:Math ととる。

上記以外の場合、すなわち テンプレート:Mvar が テンプレート:Mvar の倍数の場合は初期値 テンプレート:Math を決定するのはより難しくなる。

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

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

テンプレート:Mvar の値から初期値 テンプレート:Math を見出すには、リーゼルテンプレート:Sfnや Rodsethテンプレート:Sfn が示すようにリュカ数列を用いる。なおリーゼルは テンプレート:Mvar が テンプレート:Mvar で割り切れないときは テンプレート:Math ととることができ、したがって上掲の方程式を解く必要がないことを示している。初期値 テンプレート:Math はリュカ数列 テンプレート:Math を用いて テンプレート:Math ととる。この手続きに要する時間はリュカ–レーマー–リーゼル・テスト本体と比較して少なく済む。

判定法の仕組み

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

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

さて、数列 テンプレート:Mset のテンプレート:仮リンクを求める。リュカ–レーマー・テストに従い、テンプレート:Math と置くと、帰納法によって数列 テンプレート:Mset が満たすべき漸化式 テンプレート:Math が成り立つことが示される。続いて、数列 テンプレート:Math の テンプレート:Math 番目の値について考えると、これはリュカ数列であって、テンプレート:Mvar はある二次方程式の根となり、さらに テンプレート:Math という形の漸化式を満たす。実のところ、考慮すべきは テンプレート:Math 番目の値であるが、リュカ数列の テンプレート:Mvar 番目ごとの値からなる部分列は再びリュカ数列になるため、係数 テンプレート:Mvar を扱うためには異なる初期値を選択すればよい。

LLR ソフトウェア

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

参考文献

• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite journal

関連項目

• リーゼル数

外部リンク

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