フェルマー数(Fermat Number)

　「フェルマーの大定理」などで有名なフェルマーが考えた、 素数生成列(と、当人は信じていた)で

F(n) = 2 ²ⁿ + 1

　実際には F(0) から F(4) までの5つだけが素数であると判っています。 それ以外のフェルマー数はすべて、 合成数、あるいは素数か合成数かも判っていないものだけです。

どのようなことが判っているのか

　このフェルマー数についてはいくつか判っている性質があります。

めちゃめちゃ計算機にとって都合の良い形式をしている

「計算機は2進数で処理を行っている」
こともあって、 Fermat 数( 2²ⁿ+1 ) と Mersenne数( 2^q - 1 : ただし q は素数 )は、 非常に多くの人たちによって解析されています。

　これは単純に「計算機上で表現しやすい」というだけの意味ではありません。 たとえば、フェルマー数は2進数で表現すると

100000......000001 という形をしているので、 実は除算の中途状態がビットの変化パターンに収束させることができる。 このため、パターン変化を数列として捕らえることで、 循環数列を調べる、などの処理が機械的に処理できるようになります。

Fermat 数に関しての記録ページは?

Fermat factoring status というページがかなり情報を持っています。 ちなみに本ページはまだ、ここから得られた情報を反映していません。 ですので、以下の情報には、特に記録に関しては、 間違いが含まれている可能性が多分にあります。

知られている Fermat 素数は?

F(0) = 3,
F(1) = 5,
F(2) = 17,
F(3) = 257,
F(4) = 65537 だけである。

現在知られている最大の Fermat 合成数は?

F(23471) で、( 5 * (2 ²³⁴⁷³ ) + 1 ) を因数に持つ。 これは Keller によって1984年(ただし報告は 1985年)発見された。

因数が何も知られていない最小の Fermat 合成数は?

私が調べた範囲では F(14) である。 ただし、これは私の調べ方が甘いだけである可能性はある。 ちなみに、最小の素数でも 30桁はあるだろうと言われている。

素数であるか合成数であるかが知られていない、 小さな Fermat 数は?

今のところ 5 ≦ n ≦ 30 はすべて合成数であることが判っている。

F(28) は Taura によって1997年に小さな素因数が発見された。

F(22) は V. Trevisan, J.B. Carvalho によって1994年に、 Richard E. Crandall, C. Norrie, J. Young によって 1995年に、 それぞれ合成数であることが報告された。

F(24) は Richard E. Crandall, Ernst W. Mayer, Jason S. Papadopoulos によって 1999年 9月に合成数であることが報告された。 Pepin の定理が使われている。

Fermat 数が合成数か素数かを識別する方法は?

　Wilson の定理というものがある。

正の整数 n について、
( n - 1 ) ! ≡ -1 ( mod n )
が成立するならば、 n は素数である。

ただし、N! を(剰余であっても)計算する高速な方法は発見されていない。 従ってこれ自体はあまり役に立たない。

　Pepin の判定法というものがある。 1877年に発見されたもので、 Lucas が与えた Fermat の小定理の逆を使っている。

3 ^{{ ( F( n ) - 1 ) / 2 }} ≡ -1 ( mod F( n ) )
が成立するならば、F(n) は Fermat 素数である。

Fermat 数の因数について判っていることは?

すべての Fermat 数は奇数である(当たり前だね)。

---

n >= 2 であるような ( 2ⁿ + 1 ) は互いに素である。

n = 1 の場合だけが例外で、 x が整数の場合に、 ( 2 ^2*x+1 + 1 ) は 3 で割りきれる。 ただし、Fermat 数の場合 n = ( 2 ^y ) という形なので、 これと合致することはない。

---

Euler が最初に F(5) を因数分解するときに発見したものが優れている。

n >= 2 であるような F(n) のすべての因数は、 ( k * 2 ^{n + 2} ) + 1 という形をしている。ここで k は正の整数。

k = 1, 2 の場合、 この数値は (( 2 ^m ) + 1 ) の形をとる。 先のルールからも判るように、 この場合 Fermat 合成数に対する因数は、 この形をとれないので k >= 3 である。

---

k < 9*2⁽ⁿ⁺²⁾ + 6 な k について、 これが Fermat 数を割るための k として成立するならば、 k * 2⁽ⁿ⁺²⁾ + 1 は素数である。

k >= 3 である。
k が Fermat 数を割るための k として成立する上に、 k < 9*2⁽ⁿ⁺²⁾ + 6 が成立するとする。 もし、 k * 2⁽ⁿ⁺²⁾ + 1 が合成数であるならば、 Euler の定理から k * 2⁽ⁿ⁺²⁾ + 1 = (k₁ * 2⁽ⁿ⁺²⁾ + 1) *(k₂ * 2⁽ⁿ⁺²⁾ + 1) が成立するはずであり、 k₁ >= 3, k₂ >= 3 が成立するはずである。 従って k は k₁ = k₂ = 3 の時に最小値になるはずだ。 この場合、k = 9*2⁽ⁿ⁺²⁾ + 6 となる。
ということは、 k < 9*2⁽ⁿ⁺²⁾ + 6 の場合、 これが合成数だと Euler の定理を満たさない素因数が存在することになる。 これは矛盾するので、 k < 9*2⁽ⁿ⁺²⁾ + 6 が F(n) を割りきるならば、 k * 2⁽ⁿ⁺²⁾ + 1 は素数でなくてはいけない。

---

2²ⁿ + 1 の商が k₁ * 2ⁿ⁺²b + 1 という形をしている、 ということは、その商もまた k₂ * 2ⁿ⁺² + 1 という形をしている、 という意味です。 仮に、k₁ が求まったとするならば k₂ は

( 2^{2n - (n+2)} - k₁ ) / ( k₁ * 2ⁿ⁺² + 1 ) = k₂ を満たします。 つまり、

22n + 1	≡
22n - (n+2) - k1	≡	0 ( mod ( k1 * 2n+2 + 1 ))

2^{2n - (n+2)} ≡ k₁ ( mod ( k₁ * 2ⁿ⁺² + 1 ))

が成立する、ということです。 これは計算量を減らす上で重要な性質です。

---

g(n) = k*2ⁿ⁺²+1 は、次の性質を持ちます。

g(0) = 4*k+1
g(n+1) = 2*g(n)-1
∴ g(n+i) = 2ⁱg(n) - 2ⁱ⁺¹+1

∴2ⁱ⁺¹ - 1 ≡ 0 ( mod g(n))
つまりg(n) がメルセンヌ数 M(i+1) の因数であれば、 g(n+i) は g(n) で割りきることができる。

---

2ⁿ+1 同士は n >= 2 について互いに素なので、

ある Fermat 数で因数になったら、 別の Fermat 数の因数になることはできない。

---

あるフェルマー数で k が使われたとした場合に、 他のフェルマー数で同じ k が使われることはあり得る。

F(5) と F(23471) が共に同じ k = 5 を素因数に持っています。

---

2²ⁿ≡b( mod( v * 2^m * 2ⁿ⁺² + 1 )) の場合、 2²ⁿ⁺¹ ＝ (2²ⁿ)²
≡
b² ( mod ( v * 2^m * 2ⁿ⁺² + 1 )) ＝ b² ( mod ( v * 2^m-1 * 2ⁿ⁺³ + 1 ))

つまり、k = v*2^m-1 に対する剰余の演算も、 非常に高速に可能だという事になる。

---

---

役に立つかどうか判らない知識として次のようなものがあります。

---

F(m) - 2 = F(0) * F(1) * … * F(m-1)

---

n >= 3 の時に、 正 n 多角形をコンパスと定規で作図されるためには、
n = ( 2^k ) * p1 * p2 * … ph
と表される必要がある。 ここで、 k >= 0 な整数、 p1 … ph は異る Fermat 素数である。

---

Fermat 数が素因数 p を持つとき、 その Fermat 数が p² で割りきれるような Fermat 数が存在するかどうか、 する、しないのどちらも証明されていない。

---

Fermat 素数が無限にあるのかどうか判らない。

---

Fermat 合成数が無限にあるのかどうか判らない。

---

k に平方数(ある整数 x に対して x² という数字) が来るのかどうか、わからない。 今のところ、そのような k は私の探索範囲では見つかっていない。 しかし、否定するような証明も同様に見つかっていない。

---

8 <= n <= 11 の範囲に関して言えば、 F(n) は n-6 個の素数から成り立っている。

従って、その近辺の n が同じ規則にしたがっている可能性は高い。

---

k = [3 .. 67108864(65536*1024)], n = [12 .. 19] の範囲については、 GNU bc を使ったしらみつぶしが行われた。

k = [3 .. 8192], n = [20 .. 399] の範囲については、 GNU bc を使ったしらみつぶしが行われた。

結果は下記の表にあるだけ。 それ以外の k は因数として成立しなかった。 しらみつぶしに使ったスクリプトは ここ からとることができる。

---

現在判っている素因数分解結果

　素因数分解ができているフェルマー数は、実はあまり多くありません。 フェルマー数は n が大きくなると、 極めて高速に大きくなることがその原因です。 ただし因数分解ができている、 つまり素因数の一部が判っているものは多く存在します。

現在、未知の素因数候補として有効なのは、 F(12) 以上が解決していないこともあって、 ( 3 * 2^(14) + 1 ) 以上の素数です。 もっとも、実際には最小素数が求まっていないのは F(14) 以上ですので、 ( 3 * 2^(16) + 1 )以上の素数でしょうが。

　実は、Web を探してもこのフェルマー数の素因数分解結果を、 完全に記述している WebPage はほとんどありません。 大抵の場合、C251 とか P62 とかいう表現を使っています。 これは Cxxx というのが『xxx 桁の合成数』、 Pxx というのが『xx 桁の素数』という意味です。 確かに、因数分解した結果の1個所でしか使われていない表現ですので、 計算すればその値を算出することはできます。 ですので、数学的にはその表現は何ら問題ありません。

　しかし、 大きな数値を扱うためのライブラリなどを作っているプログラマから見ると、 これは非常に困った状態です。 デバッグに使うテストとして、 大きな値を持ち、 結果が判っているフェルマー数の因数分解は極めて有効だからです。

　そこでここでは、 知っている限りの素因数分解結果、 ならびに因数分解結果を可能な限り提示したいと思います。 (disk space とのご相談な部分もあるからねぇ)

　以下の表で、 赤い文字 の数値は合成数です。 緑の文字 の数値は合成数か素数か調べていないものです。 黒字(という方の文字と同じ色の部分)は素数です。 また、1行で表示しきれない場合、 複数行にまたがる形にしています。 乗算記号に * を使っているので、数字の切目は判るかと思います。

さらに可能な場合は [] の中に ( k*2^(n+2) + 1 ) の形の場合の k の値を提示します。