mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

View Poll Results: Which number next?
2^947-1 : first hole 13 68.42%
Fib(1373) : not a Mersenne number 4 21.05%
2^991-1 : interestingly large 2 10.53%
Voters: 19. You may not vote on this poll

Reply
 
Thread Tools
Old 2012-12-17, 11:21   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default Now what (VII)

2^929-1 is pretty close to completion.

So I should at least be doing the set-up for the next job.

But I'm not sure what the next job is. Hence this thread.
fivemack is offline   Reply With Quote
Old 2012-12-17, 11:55   #2
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

.
Quote:
Originally Posted by Raman View Post
2,2042 L/M SNFS 308
13,269- SNFS 300
2,991- SNFS 299
2,947- SNFS 286
2,929- SNFS 280
L1279 SNFS 268
L1277 SNFS 267
.

Last fiddled with by Raman on 2012-12-17 at 12:43
Raman is offline   Reply With Quote
Old 2012-12-17, 12:13   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×72×109 Posts
Default

My most wanted number is W(951), or 951*2^951-1, with no known factors and hence the composite is C290 as is the SNFS difficulty.

It has been run to t55 or so with ECM. Specifically, the ecmnet server records
Code:
W_951_C290 N 18101159423518357666828255177479109538365804182759476871194099689081082431482170358290624858698812024459501904953261022348573575276969028199796222497643229300730947446598839553529533129630939491374047682419407574822021491459083058737118733981076145112889022659672203022021130838051387342847
W_951_C290 P 1345898799,0,0,active,nolocalcontrol,recurse
W_951_C290 B 2000 522:0 3:0 1:0
W_951_C290 B 50000 300:0 3:0 1:0
W_951_C290 B 250000 610:0 3:0 1:0
W_951_C290 B 1000000 900:0 3:0 1:0
W_951_C290 B 3000000 2437:0 3:0 1:0
W_951_C290 B 11000000 4238:0 3:0 1:0
W_951_C290 B 43000000 7660:0 3:0 1:0
W_951_C290 B 110000000 17924:0 14:0 1:0
W_951_C290 B 260000000 0:0 3:0 1:0
for the work done to date.

As 951 == 3 mod 6, there are two obvious sextics, one which factors a C291 with a low skew polynomial and the other with higher skew on the C290. It's not at all obvious to me which is likely to be the better in practice.

Paul
xilman is offline   Reply With Quote
Old 2012-12-17, 16:51   #4
axn
 
axn's Avatar
 
Jun 2003

25·5·31 Posts
Default

Quote:
Originally Posted by xilman View Post
As 951 == 3 mod 6, there are two obvious sextics, one which factors a C291 with a low skew polynomial and the other with higher skew on the C290. It's not at all obvious to me which is likely to be the better in practice
Have you tried using msieve to score them? It is a pretty good indication as to which is better.
axn is offline   Reply With Quote
Old 2012-12-17, 22:49   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13·491 Posts
Default

msieve says 4.748e-15 for 951*2^954-8 and 5.128e-15 for 7608*2^948-1 (they obviously have the same alpha, and the first has a slightly smaller size score). There's only a factor two in skew between them, which I'd really not expect to make a large difference; with identical sieving parameters I'm seeing very similar yield (7608* is slightly higher) but have not sieved statistically significantly far.

I suspect it would take about one CPU-week on each polynomial to get statistical significance, which is an amount of effort I'm not really willing to put in - though definitely worth doing, since the full sieving would take around 80 CPU-years and getting that down to 75 would be worth it.

Last fiddled with by fivemack on 2012-12-18 at 00:12
fivemack is offline   Reply With Quote
Old 2012-12-18, 01:28   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

246728 Posts
Default

Quote:
Originally Posted by fivemack View Post
msieve says 4.748e-15 for 951*2^954-8 and 5.128e-15 for 7608*2^948-1 (they obviously have the same alpha, and the first has a slightly smaller size score). There's only a factor two in skew between them, which I'd really not expect to make a large difference; with identical sieving parameters I'm seeing very similar yield (7608* is slightly higher) but have not sieved statistically significantly far.

I suspect it would take about one CPU-week on each polynomial to get statistical significance, which is an amount of effort I'm not really willing to put in - though definitely worth doing, since the full sieving would take around 80 CPU-years and getting that down to 75 would be worth it.
I can put in the effort easily enough if there's a reasonable chance of the factorization being completed. I could almost do the full sieving myself (28 cores in my study alone) but it's just a bit too much and I'd be unable to perform the LA anyway.
xilman is offline   Reply With Quote
Old 2012-12-18, 03:50   #7
axn
 
axn's Avatar
 
Jun 2003

115408 Posts
Default

5.128/4.748=1.08

So the second is about 8% better. I'd just take these at their face value and go with that. (BTW, multiplying the skews by about 1.4 gives slightly better scores)
axn is offline   Reply With Quote
Old 2012-12-18, 08:16   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default

I will be happy to do the linear algebra for W951. It'll be comparable to the largest thing I've done so far, and I'd expect a runtime between six and twelve weeks.

I am also willing to throw in two dozen cores for a season to help with the sieving.

The 80 CPU-year figure came from grotesquely wrong parameters; I've got the estimate down to 40 years with only minor changes (this is a 3RLP 2ALP job), the question is whether this is an LP32 or an LP33 job. I'm now somewhat confident that 7608* is the way to go.
fivemack is offline   Reply With Quote
Old 2012-12-19, 19:23   #9
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

143578 Posts
Default

After a little more tedious investigation (sixteen runs):

7608*
33-bit large primes
3A2R
Sieve with 16e on rational side

Around 50 CPU-years

Last fiddled with by fivemack on 2012-12-19 at 19:23
fivemack is offline   Reply With Quote
Old 2012-12-19, 22:34   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D6C16 Posts
Default

How much more ECM work is necessary for W951? Any? I'm forgetful of the rules of thumb for these things, but t55 seems inadequate for a SNFS 290....
bsquared is offline   Reply With Quote
Old 2012-12-20, 00:56   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default

gmp-ecm reckons it would take six CPU-years for a t60 (using b1=260e6). The probability of the t60 being useful is about 8% (the probability of a factor between 55 and 60 digits is about 1-55/60); the SNFS takes 50 CPU-years; so a whole t60 is too much.

gmp-ecm reckons that a t55 would be about one CPU-year but probably less chance of being useful. If there were the chance of doing another t55 before starting SNFS then it might be reasonable, but more than that would I think be excessive.
fivemack is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 07:22.

Mon May 10 07:22:39 UTC 2021 up 32 days, 2:03, 0 users, load averages: 1.98, 1.86, 1.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.