ワグスタッフ素数とは？意味をやさしく解説

ワグスタッフ素数とは

ワグスタッフ素数（Wagstaff prime）は、数論において特定の形式を持つ素数の一つであり、次のように定義されます。

$$
p = \frac{2^q + 1}{3}$$

ここで、$q$は別の素数を指します。ワグスタッフ素数という名称は、数学者サミュエル S. ワグスタッフ・ジュニアに由来しています。本素数に関する最初の言及は、1990年にフランソワ・モランがEurocryptにおいて行った講演によって広まりました。この素数は新メルセンヌ予想と関連があり、特に暗号理論において重要な役割を担っています。

主なワグスタッフ素数

初めて発見されたワグスタッフ素数は以下の通りです：

- 3
- 11
- 43

これらはその定義に基づき、以下のように計算されます。

- 3 = \frac{2^3 + 1}{3}
- 11 = \frac{2^5 + 1}{3}
- 43 = \frac{2^7 + 1}{3}

最初のワグスタッフ素数としては、これらの数が知られており、さらに多くのワグスタッフ素数が存在します。オンライン整数列大辞典によると、最初のいくつかは次の通りです：3, 11, 43, 683, 2731, 43691, 17 4763, 2 796203, 71 5827883, 293 2031007403などの数が知られています。

発見と開発

2013年10月時点では、次のような$ q $の値がワグスタッフ素数または確率的素数（PRP）として知られています：
3, 5, 7, 11, 13, 17, 19, 2 3, 31, 43, 61, 79, 101, 127, 167, 191, 199, 3 13など。最も近年の発見として、2010年2月にTony Reixが発見した次のワグスタッフ確率的素数が示されています。

$$
\frac{2^{403 1399} + 1}{3}
$$

これは12万桁を超える数で、発見時点で3番目に大きな確率的素数でした。さらに2013年には、Ryan Propperによってさらに2つのワグスタッフ確率的素数が見つかりました。これらはいずれも400万桁をわずかに超える桁数を持つものでした。

素数判定

ワグスタッフ素数の判定に関して、$ q $が83 3 39以下の場合は素数であることが証明されていますが、これを超える場合は確率的素数とされます。2007年には、François Morainが$ q = 42737 $の時の素数であることを証明するに至りました。この証明には743 GHz-daysの計算力を要しました。

現在知られているアルゴリズムの中では、ECPP（Elliptic Curve Primality Proving）がワグスタッフ数の素数判定において最も効率的とされています。また、Jean PennéによるLLR（Lucas-Lehmer-Riesel）ツールもワグスタッフ確率的素数を見つけるのに使われています。この工具は、特定の数学的条件に基づく周期性を利用しています。

一般化

ワグスタッフ素数のさらに一般的な形式も考えられます。それは次のように定義されます。

$$
Q(b,n) = \frac{b^n + 1}{b + 1}
$$

ここで、$b \geq 2$の条件が必要です。これに関連する問題として、特定の$ b $の値を持つ場合にこの数式が全て合成数となるかどうかが研究されています。興味深いことに、興味のある各$ b $について、$ n $が奇数である限り、素数が存在する可能性が提示されています。

このように、ワグスタッフ素数は数論だけでなく、暗号理論にも大きな影響を及ぼす重要な数群であり、さらに多くの研究が期待されています。

もう一度検索