Index of /WallStreet/6351/gfn/fermat
Name Last modified Size Description
![[DIR]](/icons/back.gif)
Parent Directory 16-Oct-2009 18:35 -
![[ ]](/icons/binary.gif)
1277444.32768.bin 26-Apr-2009 18:23 649k
![[ ]](/icons/c.gif)
1277444.32768.gmp.c 15-Apr-2009 10:24 1k
![[ ]](/icons/unknown.gif)
1277444.32768.hex 26-Apr-2009 18:23 162k
857678.65536.bin 26-Apr-2009 18:23 1.2M
857678.65536.gmp.c 16-Apr-2009 03:00 1k
857678.65536.hex 26-Apr-2009 18:23 315k
f11.gmp.c 13-Apr-2009 12:48 1k
f11.input.bin 17-Apr-2009 11:15 2k
f11.input.hex 13-Apr-2009 12:49 1k
f19.gmp.c 18-Jul-2009 10:44 2k
f19.input.bin 18-Jul-2009 10:44 512k
f19.input.hex 18-Jul-2009 10:44 128k
f25.4th.cofactor.dec 17-Apr-2009 17:02 9.6M
f25.4th.cofactor.dec..> 17-Apr-2009 14:26 1k
f25.genefer.save 10-Jun-2009 15:13 55.0M
f25.genefer.save.dou..> 02-Aug-2009 05:51 55.0M
f25.gmp.c 13-Apr-2009 12:23 1k
f25.input.bin 13-Apr-2009 15:13 32.0M
f25.input.hex 13-Apr-2009 12:23 8.0M
f25.ps3.f.patch 18-Jul-2009 15:34 57k
hextobin.c 18-Jul-2009 10:44 1k
--- Fermat Euler Theorem for Fermat number F25 on Play Station 3 ---
---Files
[TXT] 1277444.32768.bin :1277444^32768 bindata
[TXT] 1277444.32768.gmp.c :source code(x86/linux) for 1277444^32768 hexdata
[TXT] 1277444.32768.hex :1277444^32768 hexdata
[TXT] 857678.65536.bin :857678^65536 bindata
[TXT] 857678.65536.gmp.c :source code(x86/linux) for 857678^65536 hexdata
[TXT] 857678.65536.hex :857678^65536 hexdata
[TXT] f11.gmp.c :source code(x86/linux) for f11.input.hex
[TXT] f11.input.bin :((2^(2^11)+1)/319489/974849/167988556341760475137/3560841906445833920513-1)*(319489-1)*(974849-1)*(167988556341760475137-1)*(3560841906445833920513-1) bindata
[TXT] f11.input.hex :((2^(2^11)+1)/319489/974849/167988556341760475137/3560841906445833920513-1)*(319489-1)*(974849-1)*(167988556341760475137-1)*(3560841906445833920513-1) hexdata
[TXT] f19.input.bin :((2^(2^19)+1)/70525124609/646730219521/37590055514133754286524446080499713-1)*70525124608*646730219520*37590055514133754286524446080499712) bindata
[TXT] f19.input.hex :((2^(2^19)+1)/70525124609/646730219521/37590055514133754286524446080499713-1)*70525124608*646730219520*37590055514133754286524446080499712) hexdata
[TXT] f25.4th.cofactor.dec :(2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1) decdata(10100852 Digits)
[TXT] f25.4th.cofactor.dec.gmp.c :source code(x86/linux) for (2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1) decdata
[TXT] f25.genefer.save :F25 test intermediate file when 33550002 iteration
[TXT] f25.genefer.save.double-check:F25 test intermediate file when 33550002 iteration(double check)
[TXT] f25.gmp.c :source code(x86/linux) for f25.input.hex
[TXT] f25.input.bin :((2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1)-1)*48413*2^29*1522849979*2^27*16168301139*2^27 bindata
[TXT] f25.input.hex :((2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1)-1)*48413*2^29*1522849979*2^27*16168301139*2^27 hexdata
[TXT] f25.ps3.f.patch :source code(Play Station 3/linux/Fedora 9/Cell SDK 3.1/FFTW 3.2.1) for Fermat Euler test
[TXT] hextobin.c :source code(x86/linux) for hex to bin convert
---Introduction
http://www.prothsearch.net/fermat.html
Summary of factoring status for Fermat numbers Fm as of April 2, 2009
Three prime factors known m = 15*,25
*Cofactor composite
4th cofactor of Fermat 25 is unknown composite or not.
Fermat Euler Theorem.
p1,p2,p3: prime
F = p1*p2*p3*C
p1 != p2,p1 != p3,p2 != p3,C != p1,C != p2,C != p3
GCD(F,3)=1
if 3^((p1-1)*(p2-1)*(p3-1)*(C-1)) != 1 (mod F),C is composite;otherwise C is composite or prime.
"Mathematics of Cipher P.175" shin hitomatsu 1980 ISBN-13: 978-4061180215
---News
[08/04/09]: f25.gmp.c have bug,but same output.
[08/02/09]: start Fermat Test for 2nd cofactor of Fermat number F26 on Play Station 3(http://netnews.gotdns.org/WallStreet/6351/gfn/fermat.f26/)
[08/02/09]: F25 test double check end. 4th cofactor of Fermat 25 is composite.
[06/10/09]: F25 test double check start.
[06/10/09]: F25 test end. 4th cofactor of Fermat 25 is composite.
[04/26/09]: F25 test status.(1710002/33554429)
[04/25/09]: program convert to PlayStation 3.
[04/25/09]: F25 test status.(1270002/33554429)
[04/24/09]: F25 test status.(1130002/33554429)
[04/14/09]: F25 test start.(1/33554429)
[04/09/09]: start.
---F10 result
F10 = 45592577 6487031809 4659775785220018543264560743076778192897 P252
TEST 3^((2^(2^10)+1)/45592577/6487031809/4659775785220018543264560743076778192897-1)*(45592577-1)*(6487031809-1)*(4659775785220018543264560743076778192897-1) = 1 (mod 2^(2^10)+1)
ps3$ echo "obase=2; ibase=10;((2^(2^10)+1)/45592577/6487031809/4659775785220018543264560743076778192897-1)*(45592577-1)*(6487031809-1)*(4659775785220018543264560743076778192897-1)"|bc|perl -pe "s/.\n//" > f10.input.bin
ps3$ echo "2 1024" > input
ps3$ time ./f25.ps3.a.out < f10.input.bin input
GeneFer 1.3 Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.
Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode
2^1024+1 is a probable prime. (err = 8.88e-16)
real 0m1.122s
user 0m0.342s
sys 0m0.064s
3^((2^(2^10)+1)/45592577/6487031809/4659775785220018543264560743076778192897-1)*(45592577-1)*(6487031809-1)*(4659775785220018543264560743076778192897-1) = 1 (mod 2^(2^10)+1)
P252 is 3-PRP.
---F11 result
F11 = 319489 974849 167988556341760475137 3560841906445833920513 P564
TEST 3^(((2^(2^11)+1)/319489/974849/167988556341760475137/3560841906445833920513-1)*(319489-1)*(974849-1)*(167988556341760475137-1)*(3560841906445833920513-1)) = 1 mod (2^(2^11)+1).
x86$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/f11.gmp.c
x86$ cc f11.gmp.c -lgmp
x86$ ./a.out > f11.input.hex
x86$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/hextobin.c
x86$ cc -o hextobin.out hextobin.c
x86$ ./hextobin.out < f11.input.hex > f11.input.bin
ps3$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/f25.ps3.f.patch
ps3$ wget http://pagesperso-orange.fr/yves.gallot/primes/genefer.c
ps3$ wget http://www.cellperformance.com/public/attachments/cp_hugemem.c
ps3$ wget http://www.cellperformance.com/public/attachments/cp_hugemem.h
ps3$ patch < f25.ps3.f.patch
ps3$ mv genefer.c f25.ps3.f.c
ps3$ gcc -std=gnu99 -DHAVE_CONFIG_H -O3 -fomit-frame-pointer -fstrict-aliasing -mcpu=cell -c f25.ps3.f.c
ps3$ gcc -std=gnu99 -I . -DHAVE_CONFIG_H -O3 -fomit-frame-pointer -fstrict-aliasing -mcpu=cell -m32 -c cp_hugemem.c
ps3$ gcc -std=gnu99 -O3 -fomit-frame-pointer -fstrict-aliasing -ffast-math -mcpu=cell -o f25.ps3.f.out f25.ps3.f.o cp_hugemem.o -lfftw3 -lspe2 -lm
ps3# mkdir -p /huge
ps3# mount -t hugetlbfs nodev /huge
ps3# echo 2 > /proc/sys/vm/nr_hugepages
ps3# chown root:root /huge
ps3# chmod 775 /huge
ps3$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/f11.input.bin
ps3$ echo "2 2048" > input
ps3$ time ./f25.ps3.f.out < f11.input.bin input
GeneFer 1.3 Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.
Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode
Start test of file 'input'.
Testing 2^2048+1... 1000 err= 3.55e-15
2000 err= 3.55e-15
2^2048+1 is a probable prime. (err = 3.55e-15)
real 0m0.685s
user 0m0.618s
sys 0m0.044s
3^(((2^(2^11)+1)/319489/974849/167988556341760475137/3560841906445833920513-1)*(319489-1)*(974849-1)*(167988556341760475137-1)*(3560841906445833920513-1)) = 1 mod (2^(2^11)+1).
P564 is 3-PRP.
---1277444^32768+1 result
x86$ cc 1277444.32768.gmp.c -lgmp
x86$ ./a.out > 1277444.32768.hex
x86$ cc -o hextobin.out hextobin.c
x86$ ./hextobin.out < 1277444.32768.hex > 1277444.32768.bin
ps3$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/1277444.32768.bin
ps3$ echo "1277444 32768" > input
ps3$ time ./f25.ps3.f.out < 1277444.32768.bin input
GeneFer 1.3 Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.
Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode
Start test of file 'input'.
Testing 1277444^32768+1... 1000 err= 1.16e-10
2000 err= 1.16e-10
...
664000 err= 1.16e-10
1277444^32768+1 is a probable prime. (err = 1.16e-10)
real 17m39.658s
user 17m11.501s
sys 0m26.859s
3^(1277444^32768) = 1 (mod 1277444^32768+1).
1277444^32768+1 is 3-PRP.
---857678^65536+1 result
ps3$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/857678.65536.bin
ps3$ echo "857678 65536" > input
ps3$ time ./f25.ps3.f.out < 857678.65536.bin input
GeneFer 1.3 Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.
Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode
Start test of file 'input'.
Testing 857678^65536+1... 1000 err= 5.82e-11
2000 err= 5.82e-11
...
1291000 err= 5.82e-11
857678^65536+1 is a probable prime. (err = 5.82e-11)
real 67m53.599s
user 66m5.720s
sys 1m45.316s
3^(857678^65536) = 1 (mod 857678^65536+1).
857678^65536+1 is 3-PRP.
---F19 result
Test 3^(((2^(2^19)+1)/70525124609/646730219521/37590055514133754286524446080499713-1)*70525124608*646730219520*37590055514133754286524446080499712) = 1 (mod 2^(2^19)+1).
ps3$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/f19.input.bin
ps3$ echo "65536 32768" > input
ps3$ ./f25.ps3.f.out < f19.input.bin input
GeneFer 1.3 (standard) Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.
Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode
Start test of file 'input'.
521000 err= 3.64e-12...
522000 err= 3.64e-12
523000 err= 3.64e-12
524000 err= 3.64e-12
65536^32768+1 is composite (err = 1.68e-04).
3^(((2^(2^19)+1)/70525124609/646730219521/37590055514133754286524446080499713-1)*70525124608*646730219520*37590055514133754286524446080499712) != 1 (mod 2^(2^19)+1).
C157770 is composite.
---F25 result
Test 3^(((2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1)-1)*48413*2^29*1522849979*2^27*16168301139*2^27) = 1 (mod 2^(2^25)+1).
ps3$ wget http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/f25.input.bin
ps3$ echo "65536 2097152" > input
ps3$ ./f25.ps3.f.out < f25.input.bin input
GeneFer 1.3 (standard) Copyright (C) 2001-2002, Yves GALLOT
A program for finding large probable generalized Fermat primes.
Usage: GeneFer -b run bench
GeneFer -t run test
GeneFer <filename> test <filename>
GeneFer use interactive mode
Start test of file 'input'.
3 err= 0.00e+00
4 err= 0.00e+00
...
65536^2097152+1 is a probable composite (err = 7.28e-12).
Elaps time 41 days.
3^(((2^(2^25)+1)/(48413*2^29+1)/(1522849979*2^27+1)/(16168301139*2^27+1)-1)*48413*2^29*1522849979*2^27*16168301139*2^27) != 1 (mod 2^(2^25)+1).
4th cofactor of Fermat 25 is composite.
---f25.gmp.c bug
10 mpz_mul(f,f,f);
11 }
mpz_add_ui(f,f,1); // bug but result is correct.
12 /*gmp_printf ("%Zx\n", f);*/
---Links
http://books.google.com/books?id=RbEz-_D7sAUC&pg=PA219&lpg=PA219&dq=suyama+method+composite+cofactor&source=bl&ots=Klo5DSnOJh&sig=AkukyTI_P-277QmYCYo6wO9NP0w&hl=en&ei=eiXnSY-7CoOIkQX26NSSBw&sa=X&oi=book_result&ct=result&resnum=6
http://books.google.com/books?id=6JCBqZ0CMqgC&pg=PA46&lpg=PA46&dq=Williams++1998+suyama&source=bl&ots=CHX1iHmML3&sig=I8fC6hvXj02CHcf6WCheIv1kN30&hl=en&ei=0zPnSc3YLZCPkAXV1-iWBw&sa=X&oi=book_result&ct=result&resnum=6#PPA47,M1
http://uk.playstation.com/games-media/news/articles/detail/item229653/Entertainment-on-PS3-has-a-new-look/ Removal of Install Other OS feature
http://cellperformance.beyond3d.com/articles/2007/01/howto-huge-tlb-pages-on-ps3-linux.html HowTo: Huge TLB pages on PS3 Linux
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0104&L=nmbrthry&T=0&F=&S=&P=1822 46931635677864055013377 divides 2^(2^31)+1
http://www.mail-archive.com/prime@hogranch.com/msg01313.html [Prime] Cell processor
http://www.mail-archive.com/mersenne@base.com/msg02663.html Re: Mersenne: Pepin's Test, etc.
http://www.factordb.com/search.php?query=F19&reportfac=
http://mersenneforum.org/showthread.php?t=7031 Brent-Suyama extension
http://mersenneforum.org/showthread.php?t=11328 GIMPS on PS3
http://mersenneforum.org/showthread.php?t=12168 GIMPS' first Fermat factor!
http://pagesperso-orange.fr/yves.gallot/primes/
http://mathworld.wolfram.com/FermatNumber.html is the factored part of F_n=FC (where C is the cofactor to be tested for primality), compute
http://www.prothsearch.net/fermat.html Prime factors k 2n + 1 of Fermat numbers Fm and complete factoring status Compiled by Wilfrid Keller
http://hogranch.com/mayer/F24.pdf THE TWENTY-FOURTH FERMAT NUMBER IS COMPOSITE R. E. Crandall, E. W. Mayer and J. S. Papadopoulos
http://www.fftw.org/
http://gmplib.org/
---Thanks
Thanks to Yves GALLOT san for writing genefer.c.
---
Syoichiro Yamada "msft" at "netnews.gotdns.org" (http://primes.utm.edu/bios/page.php?id=659)