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

 2010-01-25, 20:23 #1 ET_ Banned     "Luigi" Aug 2002 Team Italia 113718 Posts New Fermat factor! Today, January 25th 2010 Sergei Maiorov found the first Fermat factor of 2010 using Fermat.exe 4.4: 84977118993.2^520+1 divides F_517 ! Congratulations go to Sergei and the 100 other FermatSearch followers! Luigi
 2010-01-25, 21:45 #2 TimSorbet Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 102678 Posts Congrats to all! The size of these numbers and factors is truly astounding compared even to the largest Mersenne numbers being worked on. The number of digits in the number of digits in F_517 is 156, (if I understand this page at Wolfram Alpha correctly) and the factor is 168 digits, or 557 bits, long! Incredible. (I was going to ask if anybody had tried proving the cofactor composite/prime before I noticed how big F_517 is...now I see that'll probably have to wait a few centuries) Last fiddled with by TimSorbet on 2010-01-25 at 21:48
2010-01-25, 22:11   #3
ewmayer
2ω=0

Sep 2002
República de California

5×2,351 Posts

Nice - but ...

Quote:
 Originally Posted by Mini-Geek Congrats to all! The size of these numbers and factors is truly astounding compared even to the largest Mersenne numbers being worked on. The number of digits in the number of digits in F_517 is 156, (if I understand this page at Wolfram Alpha correctly) and the factor is 168 digits, or 557 bits, long!
Well, come on now, for this kind of trial factoring one never deals with the huge number F_{whatever} itself, only with {whatever + a few dozen}-bit-sized numbers. It's all about the amount of work needed to find the factor - for a factor of form k*2^n + 1, the work is roughly proportional to

k * n * (effort to multiply a pair of n-bit integers).

I don't mean to kill anyone's enthusiasm here, just to suggest that the excitement be somewhat proportional to the magnitude of the accomplishment, rather than the Fermat number in question, whose magnitude is a very misleading measure in this respect.

-Ernst

 2010-01-28, 09:44 #4 Joshua2     Sep 2004 13×41 Posts I read no new largest composite fermat has been found for almost 10 years. It seems like it should be easy to test if arbitrary large numbers are divisible by primes up to 30 and show that almost all fermats are composite? or do they not follow regular rules. I'd like to break that record if it would just be less than a few cpu weeks.
 2010-01-28, 10:39 #5 wblipp     "William" May 2003 Near Grandkid 2·1,187 Posts Fermat Numbers belong the class of numbers a^b +/- 1. It's known that factors either divide b or are b*k+1. b is pretty large pretty quickly for Fermat numbers. William
2010-01-28, 17:05   #6
jyb

Aug 2005
Seattle, WA

2·13·71 Posts

Quote:
 Originally Posted by Joshua2 It seems like it should be easy to test if arbitrary large numbers are divisible by primes up to 30
Do you really mean 30 here, or do you mean 30 digits? "Testing" primes up to 30 (by which I assume you mean trial division) wouldn't be very useful. It is easy to prove that no prime less than 30 can possibly divide a Fermat number F_n with n > 3.

If you meant 30 digits, I can only suggest that you try it since it's so easy. The smallest Fermat number of unknown character (i.e. prime vs. composite) is F33. Exercise: how many digits does that number have? How much memory is required to store it? How much memory does it take to run one ECM curve on it with a B1 of 250000 (the 30-digit level)? How long does that one curve take?

Quote:
 Originally Posted by Joshua2 and show that almost all fermats are composite?
What does "almost all" mean here? There are after all an infinite number of Fermat numbers. How do expect showing one of them to be composite will affect the rest?

Quote:
 Originally Posted by Joshua2 or do they not follow regular rules.
I'm not sure what you mean by "regular rules" here, but it may be useful to know that no prime can divide more than one Fermat number. E.g. 2424833 divides F_9, so it can't possibly divide any other Fermat number. Is that an example of not following regular rules in some way? Does it affect your opinion on whether it's feasible to show that "almost all" Fermat numbers are composite? <-- Note: I'm not trying to be snippy here; I really don't know what you meant by "regular rules" and "almost all" Fermat numbers, and I'm wondering if this addresses that in some way.

Quote:
 Originally Posted by Joshua2 I'd like to break that record if it would just be less than a few cpu weeks.
What record do you mean?

2010-01-28, 17:38   #7
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 Originally Posted by jyb What does "almost all" mean here? There are after all an infinite number of Fermat numbers. How do expect showing one of them to be composite will affect the rest?
IIRC, in mathematical terms, "almost all" means that an infinite number of elements of a set has got a certain property (here: is composite), and only a finite number of elements of the same set does not have this property.

I don't think that it is possible to prove that "almost all" Fermat numbers are composite by mere trial factoring.

2010-01-28, 17:43   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by Andi47 IIRC, in mathematical terms, "almost all" means that an infinite number of elements of a set has got a certain property (here: is composite), and only a finite number of elements of the same set does not have this property. .
No, this is not what it means. Almost all means that the exceptions
form a set of density 0. However, the exceptions can still form an
infinite set.

Example. Almost all integers are composite. But there are an
infinite number of exceptions.

2010-01-28, 17:45   #9
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts

Quote:
 Originally Posted by jyb Note: I'm not trying to be snippy here; I really don't know what you meant by "regular rules" and "almost all" Fermat numbers, and I'm wondering if this addresses that in some way. ?
I doubt very much whether he knows what he means by "regular rules"
and "almost all".

2010-01-28, 17:47   #10
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

24×13×29 Posts

Quote:
 Originally Posted by R.D. Silverman No, this is not what it means. Almost all means that the exceptions form a set of density 0. However, the exceptions can still form an infinite set. Example. Almost all integers are composite. But there are an infinite number of exceptions.
I thought that "almost all" would be a too imprecise phrase for you.

2010-01-28, 19:15   #11
CRGreathouse

Aug 2006

10111011000112 Posts

Quote:
 Originally Posted by henryzz I thought that "almost all" would be a too imprecise phrase for you.
I'm accustomed to it having precisely the meaning he ascribes to it.

 Similar Threads Thread Thread Starter Forum Replies Last Post Prime95 Factoring 73 2022-05-13 22:16 rajula Factoring 103 2019-03-12 04:02 ET_ Factoring 5 2011-01-13 11:40 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:37.

Mon Feb 6 15:37:37 UTC 2023 up 172 days, 13:06, 1 user, load averages: 0.74, 1.03, 1.13