リュカ擬素数

リュカ擬素数とは

リュカ擬素数とは、特定の味方の素数と極少数の合成数が通過すべきテストをクリアする合成数のことである。素数性の判定は多岐にわたるが、その中でもリュカ擬素数は独自の検定基準を持っている。特に、リュカ擬素数は素数のように振る舞う合成数であり、数学的な探求において非常に興味深い対象となる。

定義と基本的な特性

リュカ擬素数は、BaillieとWagstaffによって定義されており、自然数 P と整数 Q から derivated される。ここで、次の 式 D( = P^2 - 4Q) を定義する。また、対応するリュカ数列 U_k(P,Q)、V_k(P,Q) 小数を形成する。

自然数 n に対して、ルジャンドル記号と呼ばれる記号 (D/n) が定義され、これにより delta(n) = n - (D/n) を計算する。n が gcd(n, Q) = 1 という条件を満たす素数であるなら、次の条件が成り立つ。

$$U_{ ext{δ}(n)} ≡ 0 ext{ mod } n$$

この条件が成り立たない場合、nは素数ではないことが示され、合成数である可能性が高い。これがリュカ数列を用いた素数性判定の基盤となっている。

リュカ確率的素数と擬素数

与えられた組 (P,Q) に対して、リュカ確率的素数は、上記の条件を満たす任意の自然数 n のことである。一方、リュカ擬素数は、同じ条件を満たす正の合成数 n を指す。また、リュカテストでは、D が選択され、ルジャンドル記号が -1 になる場合に最も効果的である。この条件は、Baillie-PSW 素数テストなどの他の強力な擬素数テストとの組み合わせにおいて特に重要である。

条件が満たされる場合、(D/n) = -1 であれば、次のような条件が成り立つ。

$$U_{n+1} ≡ 0 ext{ mod } n$$

この式が成り立たない場合、n は合成数である。成り立つ場合、n はリュカ確率的素数で、生の素数、あるいはリュカ擬素数である可能性を持つ。従って、リュカ擬素数はその特性から他の確率的素数と同様に扱われ、採用時の確実性を提供する。

具体例

例1: (P,Q)=(3,-1) の場合

この場合、U の数列は標準的に次のように初期化される。

$$U_0 = 0, U_1 = 1, U_2 = 3...$$

n=19 の場合、ルジャンドル記号 (13/19) = -1 なので、

$$ ext{δ}(n) = 20$$

そして、

$$U_{20} = 6616217487 ≡ 0 ext{ mod } 19$$

したがって、19はリュカ確率的素数である。実際にこれは素数なので、リュカ擬素数ではない。

例2: (P,Q)=(3,-1) と n=119

同様に計算すると、

$$U_{120} ≡ 0 ext{ mod } 119$$

しかし、119 は 7×17 なので、合成数でありリュカ擬素数としての特性を持つ。この組に対する最小のリュカ擬素数は119である。

強いリュカ擬素数

強いリュカ擬素数は、合成数 n に対して gcd(n,D) = 1 という条件を満たし、さらに特定の式を満たす数を指す。具体的には、以下の条件を見出すことが求められる。

$$U_d ≡ 0 ext{ mod } n$$
または
$$V_{d * 2^{r}} ≡ 0 ext{ mod } n$$

また、このような数はリュカ擬素数の一部でもあるが、必ずしも逆の関係が成り立つわけではないため、強いリュカ擬素数は検定方法としてより信頼性が高い。

実装とアルゴリズム

リュカ確率的素数によるテストを行うにあたって、一般的に最初に確認するべきは n が奇数で、完全平方でないこと，以及選定された小さな素数で割り切れないことである。また、計算過程でルジャンドル記号が -1 である場合、D の選定が行われ、上記の全ての条件をまとめてチェックされる。様々なテストが行われる中で、全ての条件をクリアした上で n が合成数であることが証明されなければ、n に対する確率がより高くなる。

結論

リュカ擬素数は、その唯一な特性を持つ合成数であり、素数性テストに利用される重要な道具です。数学界においての応用可能性は広く、さらなる研究が期待されます。

もう一度検索