mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2010-10-11, 17:21   #12
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by lorgix View Post
Funny example;

M2371703 has a factor: 172106762886153056494817

The funny part is that k=
2*2*2*2*1049*1811*34469*34631, so 2kp+1 could have been found with B2= 34631
Even faster with B1=34631 and no stage 2. This 78 bit prime factor can be found in ~95 seconds on one core of a modern CPU. Pretty incredible.
Mini-Geek is offline   Reply With Quote
Old 2010-10-11, 17:58   #13
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

10011001112 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
Even faster with B1=34631 and no stage 2. This 78 bit prime factor can be found in ~95 seconds on one core of a modern CPU. Pretty incredible.
Yes, didn't think it through.

I'm doing a large number of P-1 in that exponent area with B1~ double the above, and no stage 2. Might add on stage 2 later. But as low as the limits are on some exponents in the area I think this might be a fairly effective approach.

On the other end we have M234473 with its 2kp+1=750020570278149061867959407

k= 41*234,473*161,503,549*241,537,413,779

Good luck finding that with P-1!


Would be nice to hear other more or less extreme examples, maybe that has/deserves a thread of its own.

Last fiddled with by lorgix on 2010-10-11 at 18:00 Reason: typo
lorgix is offline   Reply With Quote
Old 2010-10-12, 06:49   #14
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3×5×41 Posts
Default

My smallest factor yet;

M2428781 has a factor: 5404906126626057367

k=3*7*89*7583*78509

Evaded previous TF by 1.2bits.


Another one;

M2428661 has a factor: 1082894272153874474993

k=2*2*2*13553*22307*92177
lorgix is offline   Reply With Quote
Old 2010-10-13, 07:05   #15
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3·5·41 Posts
Default

More cases where the largest prime factor of k is relatively small:

M2430457 has a factor: 113034265381620576607487 - 77bit
k= 17*541*4987*14303*35447

M4538137 has a factor: 326333958725131675555063 - 79bit
k= 3*7*109*15271*20509*50153


Is my intuition right, or are cases like these actually quite common?
lorgix is offline   Reply With Quote
Old 2010-10-13, 08:57   #16
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

5·19·29 Posts
Default

<silverman> Read my paper with Wagstaff.</silverman>.
garo is offline   Reply With Quote
Old 2010-10-16, 12:47   #17
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

33×41 Posts
Default

Hi,

Quote:
Originally Posted by lorgix View Post
Is my intuition right, or are cases like these actually quite common?
I think so, some of "my" P-1 factors, sorted by factor size:

M49915309 has a factor: 2085962683046854861393 (70.82 Bits; k = 20895019231944 = 2 * 2 * 2 * 3 * 11 * 13 * 37 * 227 * 347 * 2089)
M50739071 has a factor: 10474816683392115991831 (73.14 Bits; k = 103222393285365 = 3 * 3 * 5 * 19 * 181 * 227 * 769 * 3821)
M51027377 has a factor: 77850684812475802805663 (76.04 Bits; k = 762832516479103 = 7 * 17 * 139 * 191 * 239 * 257 * 3931)
M51679921 has a factor: 451068222670482355938121 (78.57 Bits; k = 4364056812997860 = 2 * 2 * 3 * 5 * 11 * 307 * 953 * 2957 * 7643)
M53196851 has a factor: 129375114189794147350126111 (86.74 Bits; k = 1216003501690298805 = 3 * 5 * 11 * 17 * 71 * 79 * 2113 * 3571 * 10243)
M51007903 has a factor: 416373044176966390884620641 (88.42 Bits; k = 4081456202747311440 = 2 * 2 * 2 * 2 * 3 * 3 * 3 * 5 * 13 * 59 * 89 * 563 * 4441 * 11071)
M51094921 has a factor: 620135167283167713317314151 (89.00 Bits; k = 6068461944418778075 = 5 * 5 * 271 * 2851 * 3371 * 8429 * 11057)
M51139447 has a factor: 1873562419055481575542379948831 (100.56 Bits; k = 18318172457510946251945 = 5 * 7 * 19 * 23 * 73 * 359 * 18457 * 35597 * 69557)

Oliver
TheJudger is offline   Reply With Quote
Old 2010-10-16, 13:35   #18
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

33·72 Posts
Default

But notice the latest factors my computer found using ECM:

M400087 has a factor: 286218557414155282359049 (k = 2 ^ 2 x 3 x 41737 x 714185251333)
M400277 has a factor: 2081610233687632912124807 (k = 11 x 107 x 2209186189633807)

These factors could not have been discovered using P-1.

Last fiddled with by alpertron on 2010-10-16 at 13:36
alpertron is offline   Reply With Quote
Old 2010-10-16, 13:55   #19
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3·5·41 Posts
Default

Quote:
Originally Posted by TheJudger View Post
Hi,



I think so, some of "my" P-1 factors, sorted by factor size:

M49915309 has a factor: 2085962683046854861393 (70.82 Bits; k = 20895019231944 = 2 * 2 * 2 * 3 * 11 * 13 * 37 * 227 * 347 * 2089)
M50739071 has a factor: 10474816683392115991831 (73.14 Bits; k = 103222393285365 = 3 * 3 * 5 * 19 * 181 * 227 * 769 * 3821)
M51027377 has a factor: 77850684812475802805663 (76.04 Bits; k = 762832516479103 = 7 * 17 * 139 * 191 * 239 * 257 * 3931)
M51679921 has a factor: 451068222670482355938121 (78.57 Bits; k = 4364056812997860 = 2 * 2 * 3 * 5 * 11 * 307 * 953 * 2957 * 7643)
M53196851 has a factor: 129375114189794147350126111 (86.74 Bits; k = 1216003501690298805 = 3 * 5 * 11 * 17 * 71 * 79 * 2113 * 3571 * 10243)
M51007903 has a factor: 416373044176966390884620641 (88.42 Bits; k = 4081456202747311440 = 2 * 2 * 2 * 2 * 3 * 3 * 3 * 5 * 13 * 59 * 89 * 563 * 4441 * 11071)
M51094921 has a factor: 620135167283167713317314151 (89.00 Bits; k = 6068461944418778075 = 5 * 5 * 271 * 2851 * 3371 * 8429 * 11057)
M51139447 has a factor: 1873562419055481575542379948831 (100.56 Bits; k = 18318172457510946251945 = 5 * 7 * 19 * 23 * 73 * 359 * 18457 * 35597 * 69557)

Oliver
Quote:
Originally Posted by alpertron View Post
But notice the latest factors my computer found using ECM:

M400087 has a factor: 286218557414155282359049 (k = 2 ^ 2 x 3 x 41737 x 714185251333)
M400277 has a factor: 2081610233687632912124807 (k = 11 x 107 x 2209186189633807)

These factors could not have been discovered using P-1.

Yes, both extremes exist.

But I'm curious about how common cases like these are.

A 3D (exponent size, number of factors of k, sizes of factors of k) graph or a distribution table would be extremely nice. But I doubt that's at hand.

Any thought or info/ideas?
lorgix is offline   Reply With Quote
Old 2010-10-16, 14:17   #20
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

5×13×37 Posts
Default

not found by me but still
M52000043 has a factor : 104000087 (k=2)

thats an extreme...
firejuggler is online now   Reply With Quote
Old 2010-10-16, 14:50   #21
lorgix
 
lorgix's Avatar
 
Sep 2010
Scandinavia

3·5·41 Posts
Default

Quote:
Originally Posted by firejuggler View Post
not found by me but still
M52000043 has a factor : 104000087 (k=2)

thats an extreme...
Yeah, I've seen a few of those... Not that big before though.

A little sample; these should be the known ones in the range.

M33623 has 67247
M34283 has 68567
M34319 has 68639
M34439 has 68879
M34631 has 69263
M34883 has 69767
M35099 has 70199
M35111 has 70223
M35291 has 70583
M35831 has 71663
M35999 has 71999


And it goes on....

I think it's safe to say that k=2 is common for small p.

But just how does the distribution look? I kinda feel like this info should be available somewhere.

P.S. Smallest p for which k=2
11, 23, 83, 131, 179, 191, 239, 251, 359, 419, 431, 443

After looking those up manually I realize that this is A002515.
lorgix is offline   Reply With Quote
Old 2010-10-16, 18:12   #22
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

These "k=2" you are talking about are really k=1. Factors are of the form 2kp+1. In other words, they're mp+1, with m always even. With these factors, m=2 and k=1, since the factor is equal to 2*p+1.
I'd bet that the factors of the k's break down, on average, like the factors of any natural number of about their size. And that the chance of any given k producing a factor is related to the equation given at http://www.mersenne.org/various/math.php: "(how_far_factored-1) / (exponent times Euler's constant (0.577...))".
I don't know what that means precisely as far as how many k's will be smooth to such-and-such bounds, but the GIMPS Math page says "The chance of finding a factor and the factoring cost both vary with different B1 and B2 values. Dickman's function (see Knuth's Art of Computer Programming Vol. 2) is used to determine the probability of finding a factor, that is k is B1-smooth or B1-smooth with just one factor between B1 and B2. The program tries many values of B1 and if there is sufficient available memory several values of B2, selecting the B1 and B2 values that maximize the formula above."

Last fiddled with by Mini-Geek on 2010-10-16 at 18:18
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Turn off GCC sse-using optimizations? ewmayer Programming 3 2016-09-30 07:15
AMD goes inane jasong jasong 18 2013-11-15 22:54
When I run PRIME95, my computer threatens to turn off Rafael Information & Answers 12 2012-01-02 19:38
A fond farewell rogue Lounge 10 2008-11-21 05:25
turn off your integrated Snd card in CMOS nngs Hardware 0 2005-05-20 01:31

All times are UTC. The time now is 15:13.

Sun Sep 20 15:13:40 UTC 2020 up 10 days, 12:24, 1 user, load averages: 1.94, 1.79, 1.59

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.