New Fermat factor!

[ET_]

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

[TimSorbet]

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)

[ewmayer]

Nice - but ...

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.

Your friendly local neighborhood buzzkill,
-Ernst

[Joshua2]

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.

[wblipp]

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

[jyb]

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?

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?

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.

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?

[Andi47]

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.

[R.D. Silverman]

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.

[R.D. Silverman]

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".

[henryzz]

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.

[CRGreathouse]

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.