Factorization of Fermat Numbers: F6, F7, F8, F9, F10
[2005.07.16] Fermat数F6, F7, F8, F9, F10の素因数分解
■Fermat数
n番目のFermat数を
Fn = 2(2n)+1
とする。
0 <= n <= 10に対して、Fnを計算すると、以下のようになる。
[pari/gpによる計算]
gp> fn(n)=2^(2^n)+1
time = 3 ms.
gp> for(i=0,10,print("F_{",i,"}=",fn(i)))
F_{0}=3
F_{1}=5
F_{2}=17
F_{3}=257
F_{4}=65537
F_{5}=4294967297
F_{6}=18446744073709551617
F_{7}=340282366920938463463374607431768211457
F_{8}=115792089237316195423570985008687907853269984665640564039457584007913129639937
F_{9}=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
F_{10}=179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217
time = 28 ms.
■n=0,1,2,3,4に対して、Fnは素数である。
[pari/gpによる計算]
gp> isprime(fn(0))
time = 2 ms.
%1 = 1
gp> isprime(fn(1))
time = 10 ms.
%2 = 1
gp> isprime(fn(2))
time = 15 ms.
%3 = 1
gp> isprime(fn(3))
time = 7 ms.
%4 = 1
gp> isprime(fn(4))
time = 1 ms.
%5 = 1
■n=5,6,7,8,9,10に対して、Fnは合成数である。
n=5,6,7,8,9,10に対して、3Fn-1 mod Fnを計算すると、
3F5-1 ≡ 3029026160 ≠ 1 (mod F5)
3F6-1 ≡ 8752249535465629170 ≠ 1 (mod F6)
3F7-1 ≡ 47511664169441434718291075092691853899 ≠ 1 (mod F7)
3F8-1 ≡ 113080593127052224644745291961064595403241347689552251078258028018246279223993 ≠ 1 (mod F8)
3F9-1 ≡ 13387457852131866017809974335626508736765841341908171621341620739066502578793457441078230804865246011339933833061458906559278633032869468345609327807927612 ≠ 1 (mod F9)
3F10-1 ≡ 146809528970244036024821005514683473483244699825046485942988727983049278671435326268165085575181832374726912946280018892919388962699993405908818784177788470178225764936427450039582955979907044211973217849267621360435307454207055855850222255439616231847463892347771894224104545724927599853426578286430466818141 ≠ 1 (mod F10)
となる。ただし、≠は\not{≡}に読み換える。
Fermatの小定理より、Fn(5 <= n <= 10)は合成数であることが容易に分かる。
[pari/gpによる計算]
gp> check(a,n)=Mod(a,n)^(n-1)
time = 1 ms.
gp> check(3,fn(5))
time = 12 ms.
%7 = Mod(3029026160, 4294967297)
gp> check(3,fn(6))
time = 7 ms.
%8 = Mod(8752249535465629170, 18446744073709551617)
gp> check(3,fn(7))
time = 11 ms.
%9 = Mod(47511664169441434718291075092691853899, 340282366920938463463374607431768211457)
gp> check(3,fn(8))
time = 10 ms.
%10 = Mod(113080593127052224644745291961064595403241347689552251078258028018246279223993, 115792089237316195423570985008687907853269984665640564039457584007913129639937)
gp> check(3,fn(9))
time = 27 ms.
%11 = Mod(13387457852131866017809974335626508736765841341908171621341620739066502578793457441078230804865246011339933833061458906559278633032869468345609327807927612, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097)
gp> check(3,fn(10))
time = 100 ms.
%12 = Mod(146809528970244036024821005514683473483244699825046485942988727983049278671435326268165085575181832374726912946280018892919388962699993405908818784177788470178225764936427450039582955979907044211973217849267621360435307454207055855850222255439616231847463892347771894224104545724927599853426578286430466818141, 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217)
■n >= 2に対して、Fnの素因数pはk・2n+2+1の形に表せる。
[証明]
Fn(n >= 2)の素因数をpとする。
22n≡ -1 (mod p)
より、
22n+1≡ 1 (mod p)
である。よって、2n+1は、2 mod pの位数である。
Fermatの小定理より、
2p-1≡ 1 (mod p)
であるので、
2n+1 | p-1
となる。n >= 2より、特に、
8=23 | p-1
である。よって、
2(p-1)/2≡(2/p)≡ 1 (mod p)
より、
2n+1 | (p-1)/2
を得る。ただし、(・/・)はLegendre Symbolである。ここで、
k・2n+1 = (p-1)/2
を満たすように整数kを取ると、
p = k・2n+2+1
となる。
[(2/p)=1であることの別証明]
素数pがFn(n >= 2)の素因数であるとする。
22n ≡ -1(mod p)
より、(23・2n-2-22n-2)が2(mod p)の平方根(の１つ)であることが、以下のように確認できる。
(23・2n-2-22n-2)2 ≡ 23・2・2n-2-2・24・2n-2+22・2n-2
≡ 22n-1・(22n+1)-2・22n
≡ 22n-1・(-1+1)-2・(-1) ≡ 2 (mod p)
よって、2はmod pで平方剰余である。
■n=5,6,7,8に対して、合成数Fnを素因数分解する。
pari/gpで素因数分解すると、
F5 = 641*6700417
F6 = 274177*67280421310721
F7 = 59649589127497217*5704689200685129054721
F8 = 1238926361552897*93461639715357977769163558199606896584051237541638188580280321
となる。
ここで得られたFnの素因数をk・2n+2+1の形で表現すると、
641 = 5*27+1
6700417 = 52347*27+1
274177 = 1071*28+1
67280421310721 = 262814145745*28+1
59649589127497217 = 116503103764643*29+1
5704689200685129054721 = 11141971095088142685*29+1
1238926361552897 = 1209889024954*210+1
93461639715357977769163558199606896584051237541638188580280321 = 91271132534529275165198787304303609945362536661756043535430*210+1
となる。
[pari/gpによる計算]
gp> factor(fn(5))
time = 5 ms.
%13 =
[641 1]
[6700417 1]
gp> factor(fn(6))
time = 53 ms.
%14 =
[274177 1]
[67280421310721 1]
gp> factor(fn(7))
time = 1,534 ms.
%15 =
[59649589127497217 1]
[5704689200685129054721 1]
gp> factor(fn(8))
time = 45,863 ms.
%16 =
[1238926361552897 1]
[93461639715357977769163558199606896584051237541638188580280321 1]
F8の62桁の因数93461639715357977769163558199606896584051237541638188580280321が素数であることは、ECPP V3.4.1でこのように確認できる。
■合成数F9を素因数分解する。
GMP-ECM 6.0.1を使って、F9を素因数分解すると、
F9 = 2424833*c148
のようになる。ただし、
c148 = 5529373746539492451469451709955220061537996975706118061624681552800446063738635599565773930892108210210778168305399196915314944498011438291393118209
は148桁の合成数である。さらに、GMP-ECMでc148を素因数分解しようと１週間程度試してみたが、成功しなかった。
参考文献[2]によると、F9(c148)は1990年にLenstraにより、SNFS(特殊数体ふるい法)で完全に素因数分解されている(c148=49桁の素数*99桁の素数)。
[GMP-ECM 6.0.1による計算]
bash-2.05a$ echo 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 | ecm 500000
GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Input number is 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 (155 digits)
Using B1=500000, B2=312701712, polynomial x^1, sigma=807063132
Step 1 took 53661ms
********** Factor found in step 1: 2424833
Found probable prime factor of 7 digits: 2424833
Composite cofactor 5529373746539492451469451709955220061537996975706118061624681552800446063738635599565773930892108210210778168305399196915314944498011438291393118209 has 148 digits
■合成数F10を素因数分解する。
GMP-ECM 6.0.1を使って、F10を素因数分解すると、
F10 = 45592577*6487031809*c291
のようになる。ただし、
c291 = 607820568181834328745927047401406785398975700821911559763928675076909152806525747797078707978021962487854849079350770968904705424125269800765765006449689562590686195386366153585734177565092347016126765195631310982002631912943551551593959032889971392442015624176361633631364310142874363629569
は291桁の合成数である。さらに、GMP-ECMでc291を素因数分解しようと１週間程度試してみたが、成功しなかった。
参考文献[2]によると、F10(c291)は1995年にBrentにより、ECMで完全に素因数分解されている(c291=40桁の素数*252桁の素数)。
[GMP-ECM 6.0.1による計算]
bash-2.05a$ echo 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217 | ecm 500000
GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Input number is 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137217 (309 digits)
Using B1=500000, B2=312701712, polynomial x^1, sigma=1647556117
Step 1 took 153546ms
********** Factor found in step 1: 45592577
Found probable prime factor of 8 digits: 45592577
Composite cofactor 3942951359960012586542991835686376608231592127249807732373409846031135195659174148737161255930050543559319182152642816343958573976075461198274610155058226350701077796608546283231637018483208223116080561800334422176622099740983337736621316898600121619871377542107047343253864459964167331555646795960321 has 301 digits
bash-2.05a$ echo 3942951359960012586542991835686376608231592127249807732373409846031135195659174148737161255930050543559319182152642816343958573976075461198274610155058226350701077796608546283231637018483208223116080561800334422176622099740983337736621316898600121619871377542107047343253864459964167331555646795960321 | ecm 500000
GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Input number is 3942951359960012586542991835686376608231592127249807732373409846031135195659174148737161255930050543559319182152642816343958573976075461198274610155058226350701077796608546283231637018483208223116080561800334422176622099740983337736621316898600121619871377542107047343253864459964167331555646795960321 (301 digits)
Using B1=500000, B2=312701712, polynomial x^1, sigma=1981030128
Step 1 took 153471ms
Step 2 took 21187ms
********** Factor found in step 2: 6487031809
Found probable prime factor of 10 digits: 6487031809
Composite cofactor 607820568181834328745927047401406785398975700821911559763928675076909152806525747797078707978021962487854849079350770968904705424125269800765765006449689562590686195386366153585734177565092347016126765195631310982002631912943551551593959032889971392442015624176361633631364310142874363629569 has 291 digits
[2005.07.17追記]
GMP-ECM(B1=2000000, σ=995099801)により、c291が40桁の因数p40=4659775785220018543264560743076778192897と252桁の因数p252に分解できた。
[GMP-ECM 6.0.1による計算]
$ cat c291.txt | ecm -c 10000 2000000
GMP-ECM 6.0.1 [powered by GMP 4.1.2] [ECM]
Input number is 607820568181834328745927047401406785398975700821911559763928675076909152806525747797078707978021962487854849079350770968904705424125269800765765006449689562590686195386366153585734177565092347016126765195631310982002631912943551551593959032889971392442015624176361633631364310142874363629569 (291 digits)
Using B1=2000000, B2=2254045320, polynomial x^1, sigma=3577729791
Step 1 took 82799ms
Step 2 took 17835ms
Run 2 out of 10000:
Using B1=2000000, B2=2254045320, polynomial x^1, sigma=1754673059
Step 1 took 94586ms
Step 2 took 17235ms
....(省略)......
Step 2 took 28972ms
Run 926 out of 10000:
Using B1=2000000, B2=2254045320, polynomial x^1, sigma=1944981760
Step 1 took 127173ms
Step 2 took 29171ms
Run 927 out of 10000:
Using B1=2000000, B2=2254045320, polynomial x^1, sigma=2295402443
Step 1 took 128595ms
Step 2 took 28892ms
Run 928 out of 10000:
Using B1=2000000, B2=2254045320, polynomial x^1, sigma=995099801
Step 1 took 127503ms
Step 2 took 28952ms
********** Factor found in step 2: 4659775785220018543264560743076778192897
Found probable prime factor of 40 digits: 4659775785220018543264560743076778192897
Probable prime cofactor 130439874405488189727484768796509903946608530841611892186895295776832416251471863574140227977573104895898783928842923844831149032913798729088601617946094119449010595906710130531906171018354491609619193912488538116080712299672322806217820753127014424577 has 252 digits
ECPP V3.4.1により、p40が素数であることがこのように確認できた。
同様に、p252が素数であることがこのように確認できた。
よって、Fermat数F10=2210+1は、以下のように完全に素因数分解できた。
F10 = 45592577*6487031809*
4659775785220018543264560743076778192897*
130439874405488189727484768796509903946608530841611892186895295776832416251471863574140227977573104895898783928842923844831149032913798729088601617946094119449010595906710130531906171018354491609619193912488538116080712299672322806217820753127014424577
[参考文献]
- [1]Thomas Getgood, "Factorization Algorithms The Quadratuc Sieve", 2005, p1-9.
- [2]Richard P. Brent, "Factorization of the Tenth Fermat Number", 1999, Math. of Comp., Vol.68, No.225, p429-451.
- [3]A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, "The factorization of ninth Fermat number", 1991, p1-33.
- [4]R. P. Brent, R. E. Crandall, K. Dilcher, C. Van Halewyn, "Three new factors of Fermat numbers", 1991, p1-8.
- [5]Richard. E. Crandall, Ernst W. Mayer, Jason, S. Papadopoulos, "The Twenty-Fourth Fermat Number is Composite", 2002, Math. of Comp., Vol.72, No.243, p1555-1572.
- [6]R. P. Brent, "Factorization of th Tenth and Eleventh Fermat Numbers", 1996, p1-27.
| Last Update: 2010.01.28 |
| H.Nakao |