mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-01-25, 20:23   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12A416 Posts
Default 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
ET_ is offline   Reply With Quote
Old 2010-01-25, 21:45   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

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 Mini-Geek on 2010-01-25 at 21:48
Mini-Geek is offline   Reply With Quote
Old 2010-01-25, 22:11   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

1157110 Posts
Default

Nice - but ...

Quote:
Originally Posted by Mini-Geek View Post
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
ewmayer is offline   Reply With Quote
Old 2010-01-28, 09:44   #4
Joshua2
 
Joshua2's Avatar
 
Sep 2004

10000101012 Posts
Default

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.
Joshua2 is offline   Reply With Quote
Old 2010-01-28, 10:39   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2010-01-28, 17:05   #6
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

1,597 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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 View Post
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 View Post
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 View Post
I'd like to break that record if it would just be less than a few cpu weeks.
What record do you mean?
jyb is offline   Reply With Quote
Old 2010-01-28, 17:38   #7
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

9B216 Posts
Default

Quote:
Originally Posted by jyb View Post
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.
Andi47 is offline   Reply With Quote
Old 2010-01-28, 17:43   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Andi47 View Post
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 is offline   Reply With Quote
Old 2010-01-28, 17:45   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by jyb View Post

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".
R.D. Silverman is offline   Reply With Quote
Old 2010-01-28, 17:47   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×3×7×137 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
henryzz is offline   Reply With Quote
Old 2010-01-28, 19:15   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173316 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
CRGreathouse is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GIMPS' second Fermat factor! rajula Factoring 103 2019-03-12 04:02
GIMPS' first Fermat factor! Prime95 Factoring 72 2014-06-07 09:41
New Fermat factor found! ET_ Factoring 5 2011-01-13 11:40
New Fermat factor! ET_ Factoring 42 2008-12-01 12:50
New Fermat factor found! ET_ Factoring 3 2004-12-14 07:23

All times are UTC. The time now is 05:59.

Fri Dec 4 05:59:38 UTC 2020 up 1 day, 2:10, 0 users, load averages: 1.14, 1.10, 1.07

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.