mersenneforum.org > Data big factor
 Register FAQ Search Today's Posts Mark Forums Read

 2010-02-07, 16:42 #1 lfm     Jul 2006 Calgary 52×17 Posts big factor a p-1 run of mine just found a 165 bit factor of m(51675341)
 2010-02-07, 17:02 #2 ckdo     Dec 2007 Cleves, Germany 21116 Posts 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.
2010-02-07, 17:14   #3
lfm

Jul 2006
Calgary

1101010012 Posts

Quote:
 Originally Posted by ckdo 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?

 2010-02-07, 17:48 #4 ckdo     Dec 2007 Cleves, Germany 21116 Posts I do this manually, and I prefer to isolate the k value.
2010-02-07, 18:42   #5
lfm

Jul 2006
Calgary

52×17 Posts

Quote:
 Originally Posted by ckdo 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.

2010-02-07, 20:51   #6
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

5·223 Posts

Quote:
 Originally Posted by lfm 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.

2010-02-07, 22:17   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts

Quote:
 Originally Posted by NBtarheel_33 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

2010-02-07, 23:04   #8
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

5×223 Posts

Quote:
 Originally Posted by Mini-Geek 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.

2010-02-07, 23:35   #9
ckdo

Dec 2007
Cleves, Germany

10218 Posts

Quote:
 Originally Posted by Mini-Geek 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...

2010-02-08, 07:13   #10
S485122

Sep 2006
Brussels, Belgium

2·52·31 Posts

Quote:
 Originally Posted by lfm 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

2010-02-08, 15:16   #11
lfm

Jul 2006
Calgary

52·17 Posts

Quote:
 Originally Posted by NBtarheel_33 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 FermatSearch 2 2018-01-24 04:35 lycorn PrimeNet 11 2013-01-12 12:07 Buckle Factoring 15 2011-03-15 12:05 nfortino Data 6 2004-12-14 19:25 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