6^383+1 by GNFS (polynomial search; now complete)

fivemack · 2007-12-12, 14:45

Reservations for polynomial search - instructions in

http://www.mersenneforum.org/showpos...1&postcount=14

A million should take a few days to process; it turns out that you can start the pol51m0b and pol51opt programs simultaneously on a dual-core machine and they cooperate nicely. Haven't tried two copies of each on a quad-core: no spare quad-core.

I don't see any need to proceed beyond 25M; 6.74e-13 should take less than 4 GHz-years of sieving, and the CPU cost of finding a better one is likely to exceed the time it saves.

I note it will soon be Christmas. If anyone objects to a decision that the best polynomial posted to this thread by Thursday 20 December evening (say, 2359 GMT) will be the polynomial used for sieving, please speak now. I think getting sieving started in the copious idle time that machines tend to have over the holiday is likely to get us finished more quickly than looking for a truly superb polynomial.

Polynomial searching so far will, if I believe my model, save about 3000 GHz-hours of sieving over going with the one I first thought of; but 3000 GHz-hours is about six CPUs running from Friday evening to New Year's Day, and losing that because people haven't got jobs started before going home for Christmas would be a bit of a pity.

Code:

  0 -  1M  fivemack             Finished 0300 13/12
 1M -  2M  smh                  Finished 16/12
 2M -  3M  bsquared           Finished
 3M -  4M  smh                  Finished 16/12
 4M -  5M  CedricVonck
 5M -  7M  fivemack
 7M - 10M  JHansen            7M-9M done
10M - 11M  Andi47             
11M - 12M  Andi47             Finished 17/12
12M - 13M  Rogue
13M - 14M  Andi47
14M - 16M  dleclair
16M - 17M  jbristow
17M - 17M5 antiroach         Finished
17M5 - 18M Andi_HB
18M - 18M5 fivemack
18M5 - 19M bsquared
23M - 24M  jasonp               Finished
24M - 25M  jasonp               Finished 0330 15/12
25M - 26M  frmky                Finished  17/12
26M - 27M  frmky                Finished 18/12
31M - 31M1 axn1                 Finished 16/12

Best polynomial reported so far (andi47):

Code:

BEGIN POLY #skewness 210886.76 norm 1.11e+023 alpha -6.85 Murphy_E 6.74e-013
X5 11472718320
X4 -3795305047120954
X3 -2612363701552248486716
X2 107677876784557388243547221
X1 33277562211750204806364306268284
X0 547440910672314203689898814059115360
Y1 2391424041494417171
Y0 -7253635851193924156735160443739
M 101487845722065306796255338802878653693639562977289768772766492168634314535870484880604480822380465764353366346692160697443123034988044738084682128713493789225584005
END POLY

Andi47 · 2007-12-16, 11:18

Reserving 13M - 14M

My best polynomials so far (about halfway through the range 11-12M, both with the same X5):

Code:

BEGIN POLY #skewness 203073.58 norm 1.06e+023 alpha -6.76 Murphy_E 6.63e-013
X5 11472718320
X4 -3859896451262554
X3 -2595124187777888826700
X2 116473405723527107601148445
X1 33025156857506972682388955567940
X0 756879312929607398181057229418408064
Y1 2391424041494417171
Y0 -7253635853886667627457874178285
M 101487845722065306796255338802878653693639562977289768772766492168634314535870484880604480822380465764353366346692160697443123034988044738084682128713493789225585131
END POLY
BEGIN POLY #skewness 210886.76 norm 1.11e+023 alpha -6.85 Murphy_E 6.74e-013
X5 11472718320
X4 -3795305047120954
X3 -2612363701552248486716
X2 107677876784557388243547221
X1 33277562211750204806364306268284
X0 547440910672314203689898814059115360
Y1 2391424041494417171
Y0 -7253635851193924156735160443739
M 101487845722065306796255338802878653693639562977289768772766492168634314535870484880604480822380465764353366346692160697443123034988044738084682128713493789225584005
END POLY

axn · 2007-12-17, 04:51

Quote:

Originally Posted by frmky

I'll take 26M to 27M.

Greg

Quote:

Originally Posted by fivemack

I don't see any need to proceed beyond 25M; 6.74e-13 should take less than 4 GHz-years of sieving, and the CPU cost of finding a better one is likely to exceed the time it saves.

I guess you're better of doing one of the available ranges below 25M.

xilman · 2007-12-17, 08:32

Quote:

Originally Posted by axn1

I guess you're better of doing one of the available ranges below 25M.

And I guess the reverse.

Everything I've yet seen about polynomial searching is that, within reason, very good polynomials can occur almost anywhere. They become rarer in some areas than others but they still exist. Unless you have good reasoning to support your claim, I'd claim we're doing just that --- guessing.

I once did an exhaustive search for a cubic and a monic linear polynomial (for a very small N, clearly), minimizing the sum of the absolute values of the coefficients of the cubic. The best polynomial by far was way beyond the broad and noisy minimum at N^(1/4).

Paul

fivemack · 2007-12-17, 11:21

Quote:

Originally Posted by xilman

And I guess the reverse.

Everything I've yet seen about polynomial searching is that, within reason, very good polynomials can occur almost anywhere. They become rarer in some areas than others but they still exist. Unless you have good reasoning to support your claim, I'd claim we're doing just that --- guessing.

From my much more limited experience, you're clearly right; I was just trying to put a clear bound around the search range so that I could guarantee it would stop at some point in the near future. There are clearly some 'magic' X5 values with really good polynomials associated, and I've no idea how they're distributed.

Andi47 · 2007-12-17, 21:01

11M - 12M finished today, best polynomial at Murphy_E = 6.74e-13 which I have already posted in posting #2.

I tried to search a bit deeper for X5 = 11472718320 with pol51opt parameters -n 1e24 and N 3e21, but found no new poly above 6e-13.

Phil MjX · 2007-12-17, 22:59

Hi !

Just a short question for my own experience (and because I've seen no info about it) : do you search with the standard 60 multiplier for the a5 coefficient in pol51m0b or, for surch a large search, do you recommend to use a bigger multiplier (720 or more for extra smoothnes), as in the Chris Monico original polynomial tool in the ggnfs package ?

Regards.

ps : 11472718320 = 2^4*3^2*5*(7*19*23*5209)= 720*q

Andi47 · 2007-12-18, 05:55

My own experience is very propably much more limited than yours - this is my first use of GGNFS.

I used the parameters given here, and then I copied the lines regarding X5 11472718320 to a new 6.383a.51.m file and run

Code:

pol51opt -b 6.383a -n 1e24 -N 3e21 -e 4.5e-13

.

I had the idea to do this because 11472718320 had already yielded two polynomials with murphy_E > 6.6e-13.

jasonp · 2007-12-19, 13:37

23-24M finished, nothing better. I won't be contributing further to the search (polynomials about to get mailed though)

JHansen · 2007-12-20, 21:08

I've started to fiddle a bit with C# programming, and have now discovered Regular Expressions!

In order to do something silly, but marginally useful with RegEx'es, I've made a (very!) small console application which will parse *.cand files for easier location of the best polynomials.

All it does is scan a .cand file for polynomial pairs and print them out if they have a bigger Murphy_E value than any of the previously encountered polynomials.

In our current case, just execute "polyparse 6.383.cand" from a command line.

--
Cheers,
Jes

Andi47 · 2007-12-20, 21:22

Quote:

Originally Posted by JHansen

I've started to fiddle a bit with C# programming, and have now discovered Regular Expressions!

In order to do something silly, but marginally useful with RegEx'es, I've made a (very!) small console application which will parse *.cand files for easier location of the best polynomials.

All it does is scan a .cand file for polynomial pairs and print them out if they have a bigger Murphy_E value than any of the previously encountered polynomials.

In our current case, just execute "polyparse 6.383.cand" from a command line.

--
Cheers,
Jes

I get an error - application could not be initialized correctly.

P.S.: Finished the range 10M - 11M, no polynomials above 6e-13 in this range.

The range 13M - 14M will finish in approx. 30 - 45 minutes.

2007-12-12, 14:45	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	6^383+1 by GNFS (polynomial search; now complete) Reservations for polynomial search - instructions in http://www.mersenneforum.org/showpos...1&postcount=14 A million should take a few days to process; it turns out that you can start the pol51m0b and pol51opt programs simultaneously on a dual-core machine and they cooperate nicely. Haven't tried two copies of each on a quad-core: no spare quad-core. I don't see any need to proceed beyond 25M; 6.74e-13 should take less than 4 GHz-years of sieving, and the CPU cost of finding a better one is likely to exceed the time it saves. I note it will soon be Christmas. If anyone objects to a decision that the best polynomial posted to this thread by Thursday 20 December evening (say, 2359 GMT) will be the polynomial used for sieving, please speak now. I think getting sieving started in the copious idle time that machines tend to have over the holiday is likely to get us finished more quickly than looking for a truly superb polynomial. Polynomial searching so far will, if I believe my model, save about 3000 GHz-hours of sieving over going with the one I first thought of; but 3000 GHz-hours is about six CPUs running from Friday evening to New Year's Day, and losing that because people haven't got jobs started before going home for Christmas would be a bit of a pity. Code: 0 - 1M fivemack Finished 0300 13/12 1M - 2M smh Finished 16/12 2M - 3M bsquared Finished 3M - 4M smh Finished 16/12 4M - 5M CedricVonck 5M - 7M fivemack 7M - 10M JHansen 7M-9M done 10M - 11M Andi47 11M - 12M Andi47 Finished 17/12 12M - 13M Rogue 13M - 14M Andi47 14M - 16M dleclair 16M - 17M jbristow 17M - 17M5 antiroach Finished 17M5 - 18M Andi_HB 18M - 18M5 fivemack 18M5 - 19M bsquared 23M - 24M jasonp Finished 24M - 25M jasonp Finished 0330 15/12 25M - 26M frmky Finished 17/12 26M - 27M frmky Finished 18/12 31M - 31M1 axn1 Finished 16/12 Best polynomial reported so far (andi47): Code: BEGIN POLY #skewness 210886.76 norm 1.11e+023 alpha -6.85 Murphy_E 6.74e-013 X5 11472718320 X4 -3795305047120954 X3 -2612363701552248486716 X2 107677876784557388243547221 X1 33277562211750204806364306268284 X0 547440910672314203689898814059115360 Y1 2391424041494417171 Y0 -7253635851193924156735160443739 M 101487845722065306796255338802878653693639562977289768772766492168634314535870484880604480822380465764353366346692160697443123034988044738084682128713493789225584005 END POLY Last fiddled with by smh on 2007-12-20 at 10:50 Reason: Ultimatum

2007-12-17, 22:59	#7
Phil MjX Sep 2004 10111001₂ Posts	Hi ! Just a short question for my own experience (and because I've seen no info about it) : do you search with the standard 60 multiplier for the a5 coefficient in pol51m0b or, for surch a large search, do you recommend to use a bigger multiplier (720 or more for extra smoothnes), as in the Chris Monico original polynomial tool in the ggnfs package ? Regards. ps : 11472718320 = 2^43^25(719235209)= 720q Last fiddled with by Phil MjX on 2007-12-17 at 23:04 Reason: post scriptum*

2007-12-18, 05:55	#8
Andi47 Oct 2004 Austria 4662₈ Posts	My own experience is very propably much more limited than yours - this is my first use of GGNFS. I used the parameters given here, and then I copied the lines regarding X5 11472718320 to a new 6.383a.51.m file and run Code: pol51opt -b 6.383a -n 1e24 -N 3e21 -e 4.5e-13 . I had the idea to do this because 11472718320 had already yielded two polynomials with murphy_E > 6.6e-13.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
GNFS polynomial selection	Unregistered	Information & Answers	3	2011-04-16 14:24
GNFS polynomial degree	joral	Factoring	6	2008-09-26 22:15
5^421-1 polynomial search	fivemack	Factoring	61	2008-07-21 11:16
6^383+1 by GNFS is complete. Thanks!	fivemack	Factoring	50	2008-03-24 19:57
GNFS polynomial search tools	JHansen	Factoring	0	2004-11-07 12:15

2007-12-17, 21:01	#6
Andi47 Oct 2004 Austria 2×17×73 Posts	11M - 12M finished today, best polynomial at Murphy_E = 6.74e-13 which I have already posted in posting #2. I tried to search a bit deeper for X5 = 11472718320 with pol51opt parameters -n 1e24 and N 3e21, but found no new poly above 6e-13.

2007-12-19, 13:37	#9
jasonp Tribal Bullet Oct 2004 3,541 Posts	23-24M finished, nothing better. I won't be contributing further to the search (polynomials about to get mailed though)