mersenneforum.org GIMPS' first Fermat factor!
 Register FAQ Search Today's Posts Mark Forums Read

 2009-07-20, 04:29 #34 ATH Einyen     Dec 2003 Denmark 19×181 Posts http://primes.utm.edu/glossary/xpage/FermatNumber.html http://mathworld.wolfram.com/FermatNumber.html Fermat number Fn = 22[sup]n[/sup]+1 and it can be shown that any factor of a fermat number Fn is of the form k*2n+2+1. So you found a factor of 22[sup]19[/sup]+1 = 2524288+1 and the factor: 37590055514133754286524446080499713 = 17924335248057248252165053406 * 221+1. ( = 8962167624028624126082526703 * 222+1 factors are usually written with odd k). Here is a list of all known fermat factors: http://www.prothsearch.net/fermat.html The factor was found by Elliptic Curve Factorization Method (ECM) which is a probabilistic method: http://www.mersennewiki.org/index.php/ECM http://en.wikipedia.org/wiki/Lenstra..._factorization Last fiddled with by ATH on 2009-07-20 at 04:37
 2009-07-22, 20:21 #35 Random Poster     Dec 2008 17910 Posts Why hasn't anyone proven the compositeness of the cofactor of F25? It's been over ten years since F24 was proven composite, and computers have gotten a lot faster in that time, so it shouldn't take too much effort.
2009-07-22, 20:40   #36
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101101112 Posts

Quote:
 Originally Posted by Random Poster Why hasn't anyone proven the compositeness of the cofactor of F25? It's been over ten years since F24 was proven composite, and computers have gotten a lot faster in that time, so it shouldn't take too much effort.
Are you sure nobody has? It's certainly not a trivial effort (I'm estimating 38 days at 0.1 secs/iter on one core of my 2.5 GHz Athlon; I'd guess an i7 with all cores working on it could crank it out in under a week) but if the cofactor of F25 is still unknown it should be done.
Unless I did something wrong, this is the line you'd use in Prime95:
Code:
PRP=1,2,33554432,1,0,0,"25991531462657,204393464266227713,2170072644496392193"

 2009-07-22, 20:42 #37 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Indeed. I think that this worktodo.txt line would work Code: PRP=1,2,33554432,1,"25991531462657,204393464266227713,2170072644496392193" (please check before using it!) Expected time is 19 days on a 2.16 GHz Core 2. Very feasible, but I can't do it at the moment. Anyone want to have a go? Alex
 2009-07-23, 09:53 #38 ATH Einyen     Dec 2003 Denmark 19·181 Posts I started it, and it looks like that line works and known factors check out. Btw where is documentation for the PRP= line in Prime95? Nothing in readme.txt or undoc.txt.
2009-07-23, 12:00   #39
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts

Quote:
 Originally Posted by ATH I started it, and it looks like that line works and known factors check out. Btw where is documentation for the PRP= line in Prime95? Nothing in readme.txt or undoc.txt.
whatsnew.txt:
Code:
11) Program can now do PRP tests of (k*b^n+c)/f.  Add a line worktodo.txt that
looks like this:
PRP=k,b,n,c[,how_far_factored,tests_saved][,known_factors]
The optional how_far_factored (in bits) and tests_saved values are used
to determine if P-1 factoring prior to the PRP test would be beneficial.
The optional known_factors list is a quoted comma separated list of
known factors of k*b^n+c.

 2009-07-23, 12:01 #40 msft     Jul 2009 Tokyo 2×5×61 Posts Hi, I check 4th cofactor of Fermat 25 is conposite. 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). Use Fermat Euler Theorem. http://netnews.gotdns.org/WallStreet/6351/gfn/fermat/
2009-07-23, 12:07   #41
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by msft (mod 2^(2^25)+1).
This bit worries me. Did it really use the full Fermat number as the modulus to test whether the result is congruent to 1?

Alex

2009-07-23, 12:22   #42
msft

Jul 2009
Tokyo

61010 Posts

Quote:
 Originally Posted by akruppa Did it really use the full Fermat number as the modulus to test whether the result is congruent to 1? Alex
This is Fermat Euler Theorem.

 2009-07-23, 12:28 #43 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts Oh! Right, you multiply the exponent by p-1 for the known prime factors. That works, of course. Alex
2009-07-23, 20:40   #44
Random Poster

Dec 2008

B316 Posts

Quote:
 Originally Posted by Mini-Geek Are you sure nobody has?
Not completely sure, of course, but no one has reported it to Wilfrid Keller. I would certainly hope that any such result finds its way to his Fermat factors page.

 Similar Threads Thread Thread Starter Forum Replies Last Post rajula Factoring 103 2019-03-12 04:02 ET_ Factoring 5 2011-01-13 11:40 ET_ Factoring 21 2010-03-15 21:02 ET_ Factoring 42 2008-12-01 12:50 ET_ Factoring 3 2004-12-14 07:23

All times are UTC. The time now is 15:18.

Mon Feb 6 15:18:07 UTC 2023 up 172 days, 12:46, 1 user, load averages: 1.86, 1.64, 1.47