mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2010-02-07, 16:42   #1
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52×17 Posts
Default big factor

a p-1 run of mine just found a 165 bit factor of m(51675341)
lfm is offline   Reply With Quote
Old 2010-02-07, 17:02   #2
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

21116 Posts
Default

c165 = p75.p91 = [2 x (3 x 23 x 563 x 2591 x 1875959) x 51675341 + 1] x [2 x (4783 x 10937 x 54751 x 4189763) x 51675341 + 1]

Still a nice find.
ckdo is offline   Reply With Quote
Old 2010-02-07, 17:14   #3
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

1101010012 Posts
Default

Quote:
Originally Posted by ckdo View Post
c165 = p75.p91 = [2 x (3 x 23 x 563 x 2591 x 1875959) x 51675341 + 1] x [2 x (4783 x 10937 x 54751 x 4189763) x 51675341 + 1]

Still a nice find.
Why the extra ()s? Are they an artifact of your factoring routine?
lfm is offline   Reply With Quote
Old 2010-02-07, 17:48   #4
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

21116 Posts
Default

I do this manually, and I prefer to isolate the k value.
ckdo is offline   Reply With Quote
Old 2010-02-07, 18:42   #5
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52×17 Posts
Default

Quote:
Originally Posted by ckdo View Post
I do this manually, and I prefer to isolate the k value.
I find that rather amazing. I didn't even realize the 165 bit factor was composite when you posted the factorization. I have only the faintest glimmering of the techniques you may have used. I see the 2kp+1 patterns
now but that's about my limit.
lfm is offline   Reply With Quote
Old 2010-02-07, 20:51   #6
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5·223 Posts
Default

Quote:
Originally Posted by lfm View Post
I find that rather amazing. I didn't even realize the 165 bit factor was composite when you posted the factorization. I have only the faintest glimmering of the techniques you may have used. I see the 2kp+1 patterns
now but that's about my limit.
Oh, I think he used Prime95 as usual to find the factor, and then just ran the factor itself through a factorization program, which split the huge factor into two smaller factors. Since both of these factors are factors of a Mersenne number, we need only subtract 1 from each factor, and divide that result by 2p in order to find the k-values for each factor. It is then interesting to look at the factors of the k-values to see how "smooth" (meaning having small factors) the k-values were. In general, when we have a successful P-1 run, we find that the k-value(s) of the factor(s) found are extremely smooth. Indeed, for a factor found in Stage 1 of P-1, the k-value in a successful run will have all of its factors below the B1 bound in the P-1 assignment. For factors found in Stage 2, all but one of the factors (of the k-value) will be below B1, with the remaining factor strictly between B1 and B2. This is why there is a marginal increase in the probability of finding a factor in P-1 with an increase in the bounds B1 and B2, up to the point where you run out of RAM or the P-1 test begins to take too long to be worthwhile (i.e. you should just do the LL test).

If you are unsure how the whole GIMPS factorization process works, you should read the info on the GIMPS Web site, and ask questions. I have been GIMPSing for 8 years, but only within the last 18 months have fully understood trial factoring bit levels, P-1 bounds, etc. But as the exponents that we test get bigger (and hence require a bigger time investment for an LL test), it is essential to try and knock them out by factoring as many as possible. Factoring has likely saved tens (hundreds?) of thousands of GHz days since GIMPS began.
NBtarheel_33 is offline   Reply With Quote
Old 2010-02-07, 22:17   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Oh, I think he used Prime95 as usual to find the factor, and then just ran the factor itself through a factorization program, which split the huge factor into two smaller factors.
If so, he wasted himself quite some time.
http://www.mersenne.org/report_expon...xp_lo=51675341 gives two factors. It's pretty easy to guess that the 165-bit factor splits as these two numbers. From there, factorization is trivial. I used FactorDB when I checked, before ckdo even posted. Here are the numbers one less than the factors: 75 bits and 91 bits, or if you prefer the whole 165-bit factor.

Normally, P-1 finds one prime factor when k is smooth to the necessary limits. When two factors are smooth to those limits, it finds both at once, as their product. Their product minus one is not necessarily smooth to the necessary limits to be found alone (almost impossible for GIMPS' practical purposes). Here is the 165-bit P-1:
http://factordb.com/search.php?id=127092845

Last fiddled with by Mini-Geek on 2010-02-07 at 22:20
Mini-Geek is offline   Reply With Quote
Old 2010-02-07, 23:04   #8
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5×223 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
If so, he wasted himself quite some time.
http://www.mersenne.org/report_expon...xp_lo=51675341 gives two factors.
Yes, but I think those two factors *came from* the OP's factoring effort. The other poster, lfm, seemed like they had no idea how GIMPS finds factors, let alone how the big factors can split into two (or more) pieces, so I was trying to explain that process in more detail.

I'm thinking that there are quite a few folks running GIMPS that don't understand how the factoring process works (they just see their computer reading "Trial factoring to XX%" or doing this 3-day-long thing called P-1) and would like to learn more about it. As I said, it's only been recently (since the new assignment types have been opened up in v5) that I've really understood how the GIMPS factoring process works, and why it's so important.
NBtarheel_33 is offline   Reply With Quote
Old 2010-02-07, 23:35   #9
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

10218 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
If so, he wasted himself quite some time.
http://www.mersenne.org/report_expon...xp_lo=51675341 gives two factors.
Which is where I got them in the first place, which wasn't too time consuming. Neither was subtracting one from each and throwing them at WolframAlpha...
ckdo is offline   Reply With Quote
Old 2010-02-08, 07:13   #10
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

2·52·31 Posts
Default

Quote:
Originally Posted by lfm View Post
a p-1 run of mine just found a 165 bit factor of m(51675341)
When Prime 95 reported a 159 bit factor for M39122179 in 2007, I posted it on the forum Not quite a PrimeNet P-1 record, it turned out to be composite. I was wiser when a 175 bits factor was reported for M50996371 half a year ago (I checked with Alperton's applet and sure enough it was composite : the product of 77 and 99 bit factors.)

The biggest factors for Mersenne numbers found by P-1 factoring are :
426315489966437174530195419710289226952407399 a 149 bit factor of 17504141 (k is 124 bits) and
4212419019412230280238456118524128112421481 a 142 bit factor of 35045431 (k is 116 bits)

There are still bigger smallest non trivial (├╝berhaupt ;-) factors for Mersenne numbers but they where found by ECM or SNFS like the 324 bit factor for M727.

Jacob

Last fiddled with by S485122 on 2010-02-08 at 07:14 Reason: nimbers because of numb fingers
S485122 is offline   Reply With Quote
Old 2010-02-08, 15:16   #11
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52·17 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Oh, I think he used Prime95 as usual to find the factor,
yes, I did:
P-1 found a factor in stage #2, B1=610000, B2=16622500.
UID: xxx/antec2, M51675341 has a factor: 24202210871494586645564966315136082223034579556649, AID: xxx...
...
PrimeNet success code with additional info:
Composite factor 24202210871494586645564966315136082223034579556649 = 19514686905730497955927 * 1240204928134798557283433087


Quote:
and then just ran the factor itself through a factorization program, which split the huge factor into two smaller factors.
I think the primenet servers performed this feat somehow since mprime just reported the huge product. Is there a shortcut primenet uses as opposed to using a generalized factoring algorithm? I know its easy to decide it is composite but finding the factors seems rather harder.

Quote:
Since both of these factors are factors of a Mersenne number, we need only subtract 1 from each factor, and divide that result by 2p in order to find the k-values for each factor. It is then interesting to look at the factors of the k-values to see how "smooth" (meaning having small factors) the k-values were. In general, when we have a successful P-1 run, we find that the k-value(s) of the factor(s) found are extremely smooth. Indeed, for a factor found in Stage 1 of P-1, the k-value in a successful run will have all of its factors below the B1 bound in the P-1 assignment. For factors found in Stage 2, all but one of the factors (of the k-value) will be below B1, with the remaining factor strictly between B1 and B2. This is why there is a marginal increase in the probability of finding a factor in P-1 with an increase in the bounds B1 and B2, up to the point where you run out of RAM or the P-1 test begins to take too long to be worthwhile (i.e. you should just do the LL test).
Yes, it was stage 2 and that machine has generous memory limits. I didn't realize the p-1 stages could find composites this way.

Quote:
If you are unsure how the whole GIMPS factorization process works, you should read the info on the GIMPS Web site, and ask questions. I have been GIMPSing for 8 years, but only within the last 18 months have fully understood trial factoring bit levels, P-1 bounds, etc. But as the exponents that we test get bigger (and hence require a bigger time investment for an LL test), it is essential to try and knock them out by factoring as many as possible. Factoring has likely saved tens (hundreds?) of thousands of GHz days since GIMPS began.
I'd say I am about 16 months behind you then . I think I have figured out mostly how the trial factoring works but I haven't got into the p-1 much yet.
lfm is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new factor of F11?! siegert81 FermatSearch 2 2018-01-24 04:35
What a (TF) factor!!... lycorn PrimeNet 11 2013-01-12 12:07
New factor for F17 Buckle Factoring 15 2011-03-15 12:05
Bad Factor? nfortino Data 6 2004-12-14 19:25
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38

All times are UTC. The time now is 01:40.

Tue Aug 11 01:40:25 UTC 2020 up 24 days, 21:27, 1 user, load averages: 2.09, 2.07, 1.85

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.