5^421-1 polynomial search

[fivemack]

This will be quite a lot of work, I suspect several CPU-years; we're in territory where only the German Information Security Service admits to having gone before.

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

N 856747567165509732120757534754047466186338557004916269612235956443230634437193149247989845404816349224130750819510131856088353227722964229252203600736528648205287332264407802189199

into a file called something like 5-421.389.data

Obtain (from http://www.mersenneforum.org/showpos...10&postcount=2) the pol51m0b and pol51opt executables.

Run

pol51m0b -b 5-421.389 -p 8 -n 1e27 -a 38900000 -A 39000000

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

which will take about 36 hours on one core2/2400 core and produce a file 5-421.389.51.m with several thousand lines.

Run

pol51opt -n 3e26 -N 5e23 -b 5-421.389 -e 4.0e-14

which will take a while (I really don't know how long, possibly as much as 100 hours) and produce a file 5-421.389.cand with a widely variable number of lines, consisting of lots of blocks of the form

BEGIN POLY #skewness 896878.58 norm 5.48e+24 alpha -5.10 Murphy_E 5.67e-14
X5 2494474680
X4 -60025243754288938
X3 -3373062207827200423874
X2 35057246057064976169265284946
X1 4645652748792665336283343904631161
X0 -2514680780127600312183202859318919091241
Y1 76567071105830565601
Y0 -12798962554719076778809278463492440
M 771275635317927246367346585552260695115076213417404129525820216452123918976984444801245585894710751022186339999038527519003784741579483346878475693401519268671947976948572997457615
END POLY

Find the line beginning 'BEGIN POLY' in 5-421.389.cand with the largest Murphy_E value at the end, and, if that value is larger than the largest that's been posted here already (which is the 5.67e-14 in the previous polynomial), post the whole block here.

Repeat the whole process until July 19th or until you're fed up.

I suspect there's a polynomial with a score better than 7.0e-14 to be found, and every 0.01e-14 improvement in the score will save us something like a hundred CPU-hours at the sieving stage; we'll start sieving with the best polynomial that's been found by July 19th

Reservations

frmky *000-027(6.72) *029-041 (6.29) *066-099(6.33)
andi47 *028 *047 *048-059(6.93) *104(6.31) *105(5.47) *106(5.67) *109(5.77) *110(5.59) *111(5.10) *114(5.22) *125(4.89) *126(5.26) *129(5.34) *132(5.36) *133-139+(5.73) *142(5.51) *315(5.39) *777
batalov *042-046 *060-065(6.21) *115-124(6.33) *200-201(5.87) *420-429(5.81)
bsquared *100-101 (5.82) *102-103(5.42) *107-108(5.58) *112-113(5.62) *127-128(5.57) *130-131(5.53) *140-141(6.01) 143-144 *150-199(6.36) *450-499(6.21; maybe more) *500-599(6.41)
fivemack *350-359(6.40) *360-369(6.13) *370-379(6.15) *380-388(5.99) *389(5.46) *390(5.63) *391(5.77) *392(5.70) *393(5.43) *394(6.05) *395(5.62) *396-399(5.98) *part of 970-979 (6.09) *980-989(6.12) *990-999(5.86)

Incremental records
4 June 5.67e-14 by fivemack at X5=2494474680 (and different parameters - I'm running 0-3e7 at -p9, best was 5.81e-14)
5 June 6.35e-14 by andi47 at X5=4701325920
6 June 6.38e-14 by frmky at X5=1525027200
7 June 6.51e-14 by Batalov at X5=4329163800
7 June 6.72e-14 by frmky at X5=2676189720
30 June 6.93e-014 by andi47 at X5=5767280580

[Andi47]

Originally Posted by fivemack

Run

pol51m0b -b 5-421.389 -p 8 -n 1e27 -a 38900000 -A 39000000

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

which will take about 36 hours on one core2/2400 core and produce a file 5-421.389.51.m with several thousand lines.

Run

pol51opt -n 3e26 -N 5e23 -b 5-421.389 -e 4.0e-14

which will take a while (I really don't know how long, possibly as much as 100 hours)

pol51opt seems to be faster than pol51m0b. (core2duo @ 2 GHz)

I will increase n and N to run pol51opt in parallel to pol51m0b, I hope -n 3.5e26 -N 5.5e26 is sufficient. (further testing will be necessary.)

[frmky]

Originally Posted by Andi47

pol51opt seems to be faster than pol51m0b. (core2duo @ 2 GHz)

Usually, but not always. I'm splitting my range across 20 processor cores with each running a range of 200 a's at a time. pol51m0b takes up to a few minutes. pol51opt runs as fast or faster on most batches but pol51opt ran an hour on one batch, 45 minutes on another, and up to 30 minutes on a number of others. This is on 2GHz Opteron Barcelonas.

Greg

[Andi47]

reserving 28

edit: and increasing n and N to -n 4.5e26 -N 6.5e23 for pol51opt (I don't want it to outspeed pol51m0b when running parallelly.)

[jasonp]

Originally Posted by frmky

Usually, but not always. I'm splitting my range across 20 processor cores with each running a range of 200 a's at a time. pol51m0b takes up to a few minutes. pol51opt runs as fast or faster on most batches but pol51opt ran an hour on one batch, 45 minutes on another, and up to 30 minutes on a number of others. This is on 2GHz Opteron Barcelonas.

Greg

Most of the time that pol51opt spends is in the optimization of the polynomial roots (Murphy's 'root sieve'). If a polynomial generated from pol51m0b has unusually small size, then the root sieve can try a huge number of polynomial rotations. Actually, the code makes a number of simplifying assumptions that artificially restrict the space of polynomials that are generated, and the number of candidate polynomials found increases by a lot (about 2x) when those restrictions are removed. I've spent a lot of time in the last two months optimizing the code in pol51opt, but my changes are folded into msieve and are fairly incompatible with the GGNFS code now. Maybe I should try to backport some of them to the experimental branch of the GGNFS source.

[R.D. Silverman]

Originally Posted by jasonp

Most of the time that pol51opt spends is in the optimization of the polynomial roots (Murphy's 'root sieve'). If a polynomial generated from pol51m0b has unusually small size, then the root sieve can try a huge number of polynomial rotations. Actually, the code makes a number of simplifying assumptions that artificially restrict the space of polynomials that are generated, and the number of candidate polynomials found increases by a lot (about 2x) when those restrictions are removed. I've spent a lot of time in the last two months optimizing the code in pol51opt, but my changes are folded into msieve and are fairly incompatible with the GGNFS code now. Maybe I should try to backport some of them to the experimental branch of the GGNFS source.

Allow me to ask: Why was this number chosen? If the goal is to
tackle a ~180 digit number by GNFS, then allow me to suggest that
there are better (IMO) candidates. There are a number of numbers
in this range from the 1st edition of the Cunningham book that are still
unfactored. From an historical viewpoint, I would have to say that they
are 'better' candidates. Also, since this is the Mersenne forum, allow
me to point out that there is even a Mersenne number in this range: 2,877-.

[fivemack]

I picked 5^421-1 as the smallest Cunningham number satisfying

• More than 576 bits (174 digits)
• Prime base and exponent (the next-smaller candidate is 2^877-1)
• Clearly very much harder by SNFS than by GNFS (2^877-1 is S264, 5^421-1 is S295)

2^877-1 seems perfectly suited to Childer/Dodson's resources; it's a bit smaller than 7^313+1 which they have already reserved, though I suppose the large already-known factor makes it less exciting than the biggest numbers they're working on.

[fivemack]

I've had a look at the Cunningham Tables book, but I can't find a clear indication of what the search limits were in the first, second and third editions, apart from 'All numbers from the base 3 to base 12 tables in our first and second editions have been factored'.

Has the base-2 table always run up to 2^1200?

[R.D. Silverman]

Originally Posted by fivemack

I've had a look at the Cunningham Tables book, but I can't find a clear indication of what the search limits were in the first, second and third editions, apart from 'All numbers from the base 3 to base 12 tables in our first and second editions have been factored'.

Has the base-2 table always run up to 2^1200?

The 1925 edition (by Cunningham) has n <600. The first edition of
Brillhart et.al. extended it to 1200.

[R.D. Silverman]

Originally Posted by fivemack

I picked 5^421-1 as the smallest Cunningham number satisfying

• More than 576 bits (174 digits)
• Prime base and exponent (the next-smaller candidate is 2^877-1)
• Clearly very much harder by SNFS than by GNFS (2^877-1 is S264, 5^421-1 is S295)

2^877-1 seems perfectly suited to Childer/Dodson's resources; it's a bit smaller than 7^313+1 which they have already reserved, though I suppose the large already-known factor makes it less exciting than the biggest numbers they're working on.

Just out of curiosity: How do you plan on doing the LA? I estimate the
matrix will have about 30M rows....

[Andi47]

My best poly so far:

BEGIN POLY #skewness 519405.61 norm 2.35e+024 alpha -4.88 Murphy_E 6.35e-014
X5 4701325920
X4 -47150964287659101
X3 -15102466789075255601152
X2 10132984676580634566197564310
X1 125328000147380591200834426263986
X0 7806931538168072994169841533113060580
Y1 14205489745441387613
Y0 -11275258440050778971199095630546963
M 436601395614430864948853751861763166776593289656180372438832903491529854736236398131551339033730420628551770162585375025235916031559028217830446395115153882860149542060790848576097
END POLY

P.S.: @fivemack: I think for better clarity it is better if you collect the reservations in your starting post.