109!+1 polynomial search

fivemack · 2009-02-04, 11:01

Let's do the fourth-biggest public GNFS job yet.

EM43 is a bit bigger, but I want to reserve that for running with msieve's new polynomial selection once the parameterisation is sorted out.

Pick a number between zero and 1000 which hasn't been picked before, and post saying which you've picked; as far as I know, you're no more likely to find a good polynomial in any range than in any other. I will use '389' as the example number.

Put the line

Code:

N 144385958320249358220488210246279753379312820313396029159834075622223337844983482099636001195615259277084033387619818092804737714758384244334160217374720000000000000000000000001

into a file called something like bang109.389.data

Obtain (from http://www.mersenneforum.org/showpos...10&postcount=2, or by building them yourself from ggnfs svn) the pol51m0b and pol51opt executables.

Run

Code:

pol51m0b -b bang109.389 -p 8 -n 2e26 -a 38900000 -A 39000000

ie -a 100000X -A 100000(1+X)

which will take about 14 hours on one core2/2400 core (NB it's much quicker for smaller ranges, only about three hours for range 000) and produce a file bang109.389.51.m with between a few hundred and a few thousand lines.

Run

Code:

pol51opt -n 1e26 -N 2e23 -b bang109.389 -e 7.0e-14

which will take between a few hours and a few dozen hours, and will produce a file bang109.389.cand with a widely variable number of lines, consisting of lots of blocks of the form

Code:

BEGIN POLY #skewness 595776.02 norm 2.01e+25 alpha -6.38 Murphy_E 8.73e-14
X5 38911605600
X4 -108887534254406738
X3 169136961931062772632541
X2 25334292654996602951023137471
X1 -15547530941799324358915720760520733
X0 -1511957996366190506345629253321928760525
Y1 25670792597862397667
Y0 -1299837812369852195092370228249064
M 50224823982718742995802804137379401708408180831986072195588571703671977210660885216197454152428679820859446461925150563600872030292505341428504963761763233931421015774088825570
END POLY

These instructions changed on 13 February

If there are any lines beginning 'BEGIN POLY' in bang109.389.cand with a Murphy_E value greater than or equal to 1.00e-13 (your favourite platform's equivalent to

Code:

grep urph bang109.389.cand | sort -g -k 10 | tail

may help), post the whole block here; I'll do test sieving on them all and see which has the largest real-world yield.

Repeat the whole process until March 1st or until you're fed up.

I suspect there's a polynomial with a score better than 1.1e-13 to be found, and every 0.01e-14 improvement in the score will save us several dozen CPU-hours at the sieving stage; we'll start sieving with the best polynomial that's been found by March 1st

Reservations closed 18 February; we have 1.1e-13 polynomials coming out of our ears

Reservations

fivemack 000-009
mdettweiler 010
batalov 011
Jeff Gilchrist 012-019
batalov 020-029
Jeff Gilchrist 030-032
smh 033-035
Jeff Gilchrist 036-039
amphoria 040-042
mdettweiler 043
batalov 044-046
andi47 047
batalov 048-049
sean 050
Jeff Gilchrist 051-059
smh 060-069
amphoria 070-074
smh 075-079
Andi_HB 080-081
sean 082-087
andi47 088
batalov 090-099
bsquared 100-110
bsquared 113-200
amphoria 201-206
sean 207-218
amphoria 224-232
smh 250-254
Jeff Gilchrist 270-299
fivemack 300-399 except 333, 334
Jeff Gilchrist 400-409
Jeff Gilchrist 500-529
Jeff Gilchrist 530-549
Xyzzy 111, 112, 222, 223, 333, 334, 444, 445, 555, 556, 666, 667, 777, 778, 888 and 889.
JoeO 999-1000

Blocks done
fivemack 000-009
mdettweiler 010
batalov 011
Jeff Gilchrist 012-019
batalov 020-029
Jeff Gilchrist 030-032
smh 033-035
Jeff Gilchrist 036-039
amphoria 040-042
mdettweiler 043
batalov 044-046
batalov 048-049
sean 050
Jeff Gilchrist 051-059
smh 60-69
amphoria 70-74
smh 75-79
Andi_HB 080-081
sean 082-087
batalov 090-092
amphoria 201-206
sean 207-212
amphoria 224-229
smh 250-254
Jeff Gilchrist 290-299
fivemack 365-399
Jeff Gilchrist 400-409
Jeff Gilchrist 500-529

Incremental records

Code:

3/2 fivemack        8.56     77918820
4/2 fivemack        8.73  38911605600
5/2 batalov         9.01   2207281680
5/2 fivemack        9.03  38980754880
5/2 batalov         9.39   2050946160
5/2 Jeff Gilchrist  9.51   1955460000
5/2 smh             9.54   3320126820
6/2 batalov        10.6    2601876960
9/2 Jeff Gilchrist 11.3   50353706160
13/2 amphoria      11.5   22748948520

Andi47 · 2009-02-04, 11:08

reserving 47 (look at my nick.

)

10metreh · 2009-02-04, 12:48

How much RAM will this (the poly search) need?

Andi47 · 2009-02-04, 13:15

Quote:

Originally Posted by 10metreh

How much RAM will this (the poly search) need?

very little (I think only a few MB) when you are using a recent version of pol51m0b and pol51opt. (there was a huge memory leak in one of these, which was fixed somewhat more than a year ago.)

mdettweiler · 2009-02-04, 15:07

I'll do 010.

jasonp · 2009-02-04, 15:09

I'll get msieve v1.40 out as soon as fivemack gives me some parameters for such large jobs; the new poly selection should be run with a leading coefficient perhaps 10-100x smaller than what is being given to pol5. I can also run one or two machines locally with my local sources hacked to allow a monster-size input like this.

10metreh · 2009-02-04, 18:16

I'll take 011 (beware, I will be out quite a bit over the next few days and I have an aliquot sequence, so I may not have my results in for a while).

sean · 2009-02-04, 19:14

I will do 050. Should have more resources for this from next week.

10metreh · 2009-02-04, 19:25

I'm doing my work in 10 sections, doing pol51opt at the end of each one, so I get an idea of what sort of polys I'm getting. Also, I don't want to have to spend too much time at the end doing pol51opt, so I can turn the computer off and save energy.

mdettweiler · 2009-02-05, 01:39

My computer just got rebooted due to a power flicker in the middle of the pol51opt stage of my range. Is there anything I can do to recover the already-completed work? It had been running the pol51opt stage for at least a couple of hours.

Batalov · 2009-02-05, 03:15

Yes, there's a manual recovery --
http://www.mersenneforum.org/showpos...2&postcount=26

If you didn't redirect the output from the pol51opt then you have to check the last found X5/Y1 values from the .cand file.

I use a script like this one:

Code:

#!/bin/csh
 
set i=25
 
set j=`/bin/echo $i 1 + p |dc`
cp -p P109.389.data P109.0$i.data
nohup nice ./pol51m0b -b P109.0$i -p 8 -n 2e26 -a ${i}00000 -A ${j}00000
nohup nice ./pol51opt -n 1e26 -N 2e23 -b P109.0$i -e 7.0e-14 > P109.0$i.out &

2009-02-04, 11:01	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6454₁₀ Posts	109!+1 polynomial search Let's do the fourth-biggest public GNFS job yet. EM43 is a bit bigger, but I want to reserve that for running with msieve's new polynomial selection once the parameterisation is sorted out. Pick a number between zero and 1000 which hasn't been picked before, and post saying which you've picked; as far as I know, you're no more likely to find a good polynomial in any range than in any other. I will use '389' as the example number. Put the line Code: N 144385958320249358220488210246279753379312820313396029159834075622223337844983482099636001195615259277084033387619818092804737714758384244334160217374720000000000000000000000001 into a file called something like bang109.389.data Obtain (from http://www.mersenneforum.org/showpos...10&postcount=2, or by building them yourself from ggnfs svn) the pol51m0b and pol51opt executables. Run Code: pol51m0b -b bang109.389 -p 8 -n 2e26 -a 38900000 -A 39000000 ie -a 100000X -A 100000(1+X) which will take about 14 hours on one core2/2400 core (NB it's much quicker for smaller ranges, only about three hours for range 000) and produce a file bang109.389.51.m with between a few hundred and a few thousand lines. Run Code: pol51opt -n 1e26 -N 2e23 -b bang109.389 -e 7.0e-14 which will take between a few hours and a few dozen hours, and will produce a file bang109.389.cand with a widely variable number of lines, consisting of lots of blocks of the form Code: BEGIN POLY #skewness 595776.02 norm 2.01e+25 alpha -6.38 Murphy_E 8.73e-14 X5 38911605600 X4 -108887534254406738 X3 169136961931062772632541 X2 25334292654996602951023137471 X1 -15547530941799324358915720760520733 X0 -1511957996366190506345629253321928760525 Y1 25670792597862397667 Y0 -1299837812369852195092370228249064 M 50224823982718742995802804137379401708408180831986072195588571703671977210660885216197454152428679820859446461925150563600872030292505341428504963761763233931421015774088825570 END POLY These instructions changed on 13 February If there are any lines beginning 'BEGIN POLY' in bang109.389.cand with a Murphy_E value greater than or equal to 1.00e-13 (your favourite platform's equivalent to Code: grep urph bang109.389.cand \| sort -g -k 10 \| tail may help), post the whole block here; I'll do test sieving on them all and see which has the largest real-world yield. Repeat the whole process until March 1st or until you're fed up. I suspect there's a polynomial with a score better than 1.1e-13 to be found, and every 0.01e-14 improvement in the score will save us several dozen CPU-hours at the sieving stage; we'll start sieving with the best polynomial that's been found by March 1st Reservations closed 18 February; we have 1.1e-13 polynomials coming out of our ears Reservations fivemack 000-009 mdettweiler 010 batalov 011 Jeff Gilchrist 012-019 batalov 020-029 Jeff Gilchrist 030-032 smh 033-035 Jeff Gilchrist 036-039 amphoria 040-042 mdettweiler 043 batalov 044-046 andi47 047 batalov 048-049 sean 050 Jeff Gilchrist 051-059 smh 060-069 amphoria 070-074 smh 075-079 Andi_HB 080-081 sean 082-087 andi47 088 batalov 090-099 bsquared 100-110 bsquared 113-200 amphoria 201-206 sean 207-218 amphoria 224-232 smh 250-254 Jeff Gilchrist 270-299 fivemack 300-399 except 333, 334 Jeff Gilchrist 400-409 Jeff Gilchrist 500-529 Jeff Gilchrist 530-549 Xyzzy 111, 112, 222, 223, 333, 334, 444, 445, 555, 556, 666, 667, 777, 778, 888 and 889. JoeO 999-1000 Blocks done fivemack 000-009 mdettweiler 010 batalov 011 Jeff Gilchrist 012-019 batalov 020-029 Jeff Gilchrist 030-032 smh 033-035 Jeff Gilchrist 036-039 amphoria 040-042 mdettweiler 043 batalov 044-046 batalov 048-049 sean 050 Jeff Gilchrist 051-059 smh 60-69 amphoria 70-74 smh 75-79 Andi_HB 080-081 sean 082-087 batalov 090-092 amphoria 201-206 sean 207-212 amphoria 224-229 smh 250-254 Jeff Gilchrist 290-299 fivemack 365-399 Jeff Gilchrist 400-409 Jeff Gilchrist 500-529 Incremental records Code: 3/2 fivemack 8.56 77918820 4/2 fivemack 8.73 38911605600 5/2 batalov 9.01 2207281680 5/2 fivemack 9.03 38980754880 5/2 batalov 9.39 2050946160 5/2 Jeff Gilchrist 9.51 1955460000 5/2 smh 9.54 3320126820 6/2 batalov 10.6 2601876960 9/2 Jeff Gilchrist 11.3 50353706160 13/2 amphoria 11.5 22748948520 Last fiddled with by fivemack on 2009-02-18 at 10:12 Reason: accumulate many reservations

2009-02-04, 11:08	#2
Andi47 Oct 2004 Austria 2×17×73 Posts	reserving 47 (look at my nick. ) Last fiddled with by Andi47 on 2009-02-04 at 11:10

2009-02-05, 03:15	#11
Batalov "Serge" Mar 2008 San Diego, Calif. 3×3,469 Posts	Yes, there's a manual recovery -- http://www.mersenneforum.org/showpos...2&postcount=26 If you didn't redirect the output from the pol51opt then you have to check the last found X5/Y1 values from the .cand file. I use a script like this one: Code: #!/bin/csh set i=25 set j=`/bin/echo $i 1 + p \|dc` cp -p P109.389.data P109.0$i.data nohup nice ./pol51m0b -b P109.0$i -p 8 -n 2e26 -a ${i}00000 -A ${j}00000 nohup nice ./pol51opt -n 1e26 -N 2e23 -b P109.0$i -e 7.0e-14 > P109.0$i.out &

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Tweaking polynomial search for C197	fivemack	Msieve	38	2011-07-08 08:12
c176 polynomial search	bdodson	Msieve	45	2010-10-29 19:39
5^421-1 polynomial search	fivemack	Factoring	61	2008-07-21 11:16
6^383+1 by GNFS (polynomial search; now complete)	fivemack	Factoring	20	2007-12-26 10:36
GNFS polynomial search tools	JHansen	Factoring	0	2004-11-07 12:15

2009-02-04, 12:48	#3
10metreh Nov 2008 2·3³·43 Posts	How much RAM will this (the poly search) need?

2009-02-04, 15:07	#5
mdettweiler A Sunny Moo Aug 2007 USA 2·3,163 Posts	I'll do 010.

2009-02-04, 15:09	#6
jasonp Tribal Bullet Oct 2004 3×1,193 Posts	I'll get msieve v1.40 out as soon as fivemack gives me some parameters for such large jobs; the new poly selection should be run with a leading coefficient perhaps 10-100x smaller than what is being given to pol5. I can also run one or two machines locally with my local sources hacked to allow a monster-size input like this.

2009-02-04, 18:16	#7
10metreh Nov 2008 2×3³×43 Posts	I'll take 011 (beware, I will be out quite a bit over the next few days and I have an aliquot sequence, so I may not have my results in for a while).

2009-02-04, 19:14	#8
sean Aug 2004 New Zealand 232₁₀ Posts	I will do 050. Should have more resources for this from next week.

2009-02-04, 19:25	#9
10metreh Nov 2008 2·3³·43 Posts	I'm doing my work in 10 sections, doing pol51opt at the end of each one, so I get an idea of what sort of polys I'm getting. Also, I don't want to have to spend too much time at the end doing pol51opt, so I can turn the computer off and save energy.

2009-02-05, 01:39	#10
mdettweiler A Sunny Moo Aug 2007 USA 2×3,163 Posts	My computer just got rebooted due to a power flicker in the middle of the pol51opt stage of my range. Is there anything I can do to recover the already-completed work? It had been running the pol51opt stage for at least a couple of hours.