フェルマー数(Fermat Number)

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

F(n) = 2 2n + 1
という形式をしています。

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

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

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

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

「計算機は2進数で処理を行っている」
こともあって、 Fermat 数( 22n+1 ) と Mersenne数( 2q - 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 23473 ) + 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 であるような ( 2n + 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(n+2) + 6 な k について、 これが Fermat 数を割るための k として成立するならば、 k * 2(n+2) + 1 は素数である。
k >= 3 である。
k が Fermat 数を割るための k として成立する上に、 k < 9*2(n+2) + 6 が成立するとする。 もし、 k * 2(n+2) + 1 が合成数であるならば、 Euler の定理から
k * 2(n+2) + 1 = (k1 * 2(n+2) + 1) *(k2 * 2(n+2) + 1)
が成立するはずであり、 k1 >= 3, k2 >= 3 が成立するはずである。 従って k は k1 = k2 = 3 の時に最小値になるはずだ。 この場合、k = 9*2(n+2) + 6 となる。
ということは、 k < 9*2(n+2) + 6 の場合、 これが合成数だと Euler の定理を満たさない素因数が存在することになる。 これは矛盾するので、 k < 9*2(n+2) + 6 が F(n) を割りきるならば、 k * 2(n+2) + 1 は素数でなくてはいけない。


22n + 1 の商が k1 * 2n+2b + 1 という形をしている、 ということは、その商もまた k2 * 2n+2 + 1 という形をしている、 という意味です。 仮に、k1 が求まったとするならば k2

( 22n - (n+2) - k1 ) / ( k1 * 2n+2 + 1 ) = k2
を満たします。 つまり、
22n + 1
22n - (n+2) - k1 0 ( mod ( k1 * 2n+2 + 1 ))
22n - (n+2) ≡ k1 ( mod ( k1 * 2n+2 + 1 ))
が成立する、ということです。 これは計算量を減らす上で重要な性質です。


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

g(0) = 4*k+1
g(n+1) = 2*g(n)-1
∴ g(n+i) = 2ig(n) - 2i+1+1

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


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

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


あるフェルマー数で k が使われたとした場合に、 他のフェルマー数で同じ k が使われることはあり得る。
F(5) と F(23471) が共に同じ k = 5 を素因数に持っています。


22n≡b( mod( v * 2m * 2n+2 + 1 ))
の場合、
22n+1 = (22n)2

b2 ( mod ( v * 2m * 2n+2 + 1 )) = b2 ( mod ( v * 2m-1 * 2n+3 + 1 ))
つまり、k = v*2m-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 数が p2 で割りきれるような Fermat 数が存在するかどうか、 する、しないのどちらも証明されていない。


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


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


k に平方数(ある整数 x に対して x2 という数字) が来るのかどうか、わからない。 今のところ、そのような 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 の値を提示します。

フェルマー数因数分解
n 素因数分解完了? 既知の因数
0 ○(Fermat) 3
1 ○(Fermat) 5
2 ○(Fermat) 17
3 ○(Fermat) 257
4 ○(Fermat) 65537
5 ○(Euler) 641
[ 5 ] *
6700417
[ 52347 ]
6 ○(Landry 1880) 274177
[ 1071 ] *
67280421310721
[ 262814145745 ]
7 ○(Morrison & Brillhart 1970
連分数展開法)
59649589127497217
[ 116503103764643 ] *
5704689200685129054721
[ 11141971095088142685 ]
8 ○(Brent & Pollard 1980 rho法) 1238926361552897
[ 1209889024954 ] *
93461639715357977769163558199606896584051237541638188580280321
[ 91271132534529275165198787304303609945362536661756043535430 ]
9 ○(Western 1903)
(Lenstra & Manasse 1989 NFS法)
(Lenstra & Manasse 1989 NFS法)
2424833
[ 1184 ] *
7455602825647884208337395736200454918783366342657
[ 3640431067210880961102244011816628378312190597 ] *
74164006262753080152478714190193747405994078109751902390582131614441
5759504705008092818711693940737
[ 36212893682984902418202497163180540725583045952027296089151431452364
0507570656742232821636569307 ]
10 ○(Selfridge 1953)
(Brillhart 1962)
(Brent 1995 楕円曲線法)
(Brent 1995 楕円曲線法)
45592577
[ 11131 ] *
6487031809
[ 1583748 ] *
4659775785220018543264560743076778192897
[ 1137640572563481089664199400165229051 ] *
13043987440548818972748476879650990394660853084161189218689529577683
24162514718635741402279775731048958987839288429238448311490329137987
29088601617946094119449010595906710130531906171018354491609619193912
488538116080712299672322806217820753127014424577 [ 31845672462277390070186711131960425768214973350002903365941234320515
72662389449794290532909608718381247528904512766695430447974436372039
28438968793813706346311061025162866529618911550337779520531296860137
91147000996267651287188185111772644806400006 ]
11 ○(Cunningham 1899)
(Cunningham 1899)
(Brent 1988)
(Brent 1988)
(Brent & Morain)
319489
[ 39 ] *
974849
[ 119 ] *
167988556341760475137
[ 20506415569062558 ] *
3560841906445833920513
[ 434673084282938711 ] *
17346244717914755543025897086430977837742184472366408464934701906136
35791928791088575910383304088371779838108684515464219407129783061341
89864280826014542758708589243873685563973118948869399158545506611147
42021613255701726056413939436694579322096866510895968548270538807264
58285541519364019124649311825460928798157330577955733585049822792800
90942872567591518912118622751714319229788100979251036035496917279912
66352735878323664719315477709142774537703829458491891759032511093938
13224860442985739716507110592444621775425407069130470346646436034913
82441723306598834177
[ 21174615134173285574982784529334689743337627529744150958172243537764
10878819325059296765604619248500707810191265277666283455968973463552
12236670930193533641001695854337995073209373716881590769708870374935
81569352118776521064958422163933812649044026502558555356775560067461
64899342675004906158019179474439610349313147678168620098937771963868
29764248739735740859519803163713768591049927953187299848018697851455
88809492038969317284320651500418425949345494944448110057412733268967
44659253470441576802376843984917751190704842613684656184871137737931
9145718177075053 ]
12 ×(Lucas & Pervushin 1877)
(Western 1903)
(Western 1903)
(Hallyburton & Brillhart 1974)
( Baillie 1986 )
114689
[ 7 ] *
26017793
[ 1588 ] *
63766529
[ 3892 ] *
190274191361
[ 11613415 ] *
1256132134125569
[ 76668221077 ] *
22964766349327374158394934836882729742175302138572222575931764391308
41895160961323826592803808643123157763304539153144604501945565726378
89591520959595007811011260964956569761453380843236093912425700495914
61461009320782551308966824222425528731569111534949127744166427236012
76941820694970192991463128795367912432807840344358900154478504320924
30051766723651249856755660112961823358064264614846560708021150483896
59355236182068241950344201999449825647341556766313684295383743697537
16129841189332995025943702457251084955979786901113201153080673107947
31449989885761657097352227077484815352368256239445951125337412341600
90993221997405711848497115626313770615846340179366098118224044157942
82448107580150138831679492503454972272021823717798941515357314194439
09337015329574723107267273040294611920201206671193244090646237581464
38555005036265643143116137400042228823945740010105764278856096541459
65068254783638621003202716989623011518264972455124547591207054841845
92114074030067691647198697499592224398061647154701759458614628952014
53214517960762686355562039296307129357252744645128034273466002900209
57571600747966912966168394403107609922082657201649660373439896304215
8832323677881589363722322001921
13 ×(Hallyburton & Brillhart 1974)
(Crandall 1991)
(Crandall 1991)
(Brent 1995)
2710954639361
[ 82731770 ] *
2663848877152141313
[ 81294216221684 ] *
3603109844542291969
[ 109958186173776 ] *
319546020820551643220672513
[ 9751770654924061377584 ] *
C2391
14 × C4933
15 ×(Kraitchik 1925)
(Gostin 1987)
(Brent, Crandall, Dilcher, Van Halewyn 1997)
1214251009
[ 9264 ] *
2327042503868417
[ 17753925353 ] *
168768817029516972383024127016961
[ 1287603889690528658928101555 ] *
C9808
16 ×(Selfridge 1953)
(Crandall & Dilcher 1996)
825753601
[ 3150 ] *
188981757975021318420037633
[ 720908195400319360428 ] *
C19694
17 ×(Gostin 1998) 31065037602817
[ 59251857 ] *
N
18 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 13631489
[ 13 ] *
81274690703860512587777
[ 77509585098133576(8*29*293*1259*905678539) ] *
N
19 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 70525124609
[ 33629 ] *
N
23 × (1999 Richard McIntosh,
Claude Tardif)
167772161
[ 5 ] *
N
32 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 25409026523137
[ 1479 ] *
N
36 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 2748779069441
[ 10 ] *
N
38 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 6597069766657
[ 6 ] *
2917004348489729
[ 2653 ] *
N
39 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 46179488366593
[ 21 ] *
N
52 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 74201307460556292097
[ 4119 ] *
N
55 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 4179340454199820289
[ 29 ] *
N
58 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 219055085875300925441
[ 190 ] *
N
62 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 12857380619375557476353
[ 697 ] *
N
63 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 1328165573307087716353
[ 36 ] *
N
71 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 6450752615599935361908737
[ 683 ] *
N
73 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 188894659314785808547841
[ 5 ] *
N
77 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 256896736668108699625062401
[ 425 ] *
N
81 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。
[ 542 ] *
N
91 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 14072902366596202965053244178433
[ 1421 ] *
N
117 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 9304595970494411110326649421962412033
[ 14 ] *
N
125 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 850705917302346158658436518579420528641
[ 5 ] *
N
144 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 3032901347000164747248857685080177164813336577
[ 34 ] *
N
147 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 2230074519853062314153571827264836150598041600001
[ 3125 ] *
N
207 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 2468256835981809063232453773836025757474103798450369795022913537
[ 3 ] *
N
226 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 12940774400232307101440167241769422723345829322819474790929732919623
681
[ 30 ] *
N
228 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 10007532202846317491780396000301686906054108009647060504985660124508
9793
[ 58 ] *
N
250 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 29165132476649016722311941849063266790542377387658217067438378971993
11952805889
[ 403 ] *
N
255 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 14566644826054377384285229914092938807941364070937582956163764068195
4717087039489
[ 629 ] *
N
267 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 67158670688272274522020460450734930952286330178169667043275546196051
9645471331844097
[ 708 ] *
N
268 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 25497529210462694055817937527058685649681589762559331216430037877823
11874331836153857
[ 1344 ] *
N
284 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 13925050619474025980350702948110983522812772222325736088332991353008
465916350934514925569
[ 112 ] *
N
287 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 58833338867277759766981719955768905383883962639326234973206888466460
76849658269832556052481
[ 5915 ] *
N
298 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 20125915446184722532332243401484656231188507729419450156285067639621
28724166176665709196607489
[ 988 ] *
N
316 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 14951909251446370576765151943186864802218931656496569389629291254755
538080464483850160734608556033
[ 28 ] *
N
329 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 21190085021697819523320801576315515787541505446493442084092865634899
624656243553944189395658999345446913
[ 4844 ] *
N
692 ×特に発見できなかったので力で解いてみた。 たぶん過去に誰か計算しているだろう。 11785992004406824389661842956328288291248730120700673928938335648438
37798322189671704843408284697162353045871459337431906323416538556808
55308207599704918705294309230381221711778231966075095605883859914421
704851457
[ 1434 ] *
N
9448 ×( Keller 1980 ) [ 19 ] *
合成数
23471 ×( Keller, 1984 ) [ 5 ] *
合成数