c136
 

I used 1.39 beta 2 to search for a poly for a [URL="http://mersennewiki.org/index.php/Base_10_Still_Open#HP548"]c136[/URL]. It ran for approx. 35-36 hours (time limit was 33.88 hours) and gave me (core 2 duo, 32 bit windows):

[code]n: 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171
skew: 493321.72
c5 78120
c4 97232750889
c3 -42204187935206811
c2 59549894608656842891647
c1 4036065248257193572094637906
c0 -8667206126007101355663250669442776
Y0 -125305093374170894034075909
Y1 1184872132155583
rlim: 8000000
alim: 6000000
lpbr: 28
lpba: 28
rlambda: 2.55
alambda: 2.55
mfbr: 55
mfba: 55

skew 493321.72, size 3.398628e-014, alpha -7.037657, combined = 3.549023e-013
[/code].

This yields (sieving with gnfs-lasieve4I14e on the a side from Q=6M to 6005000): total yield: 23070, q=6005011 (0.06616 sec/rel)

I also manually started a poly search beginning from 1, this was also running approx. 35 hours and gave me this poly (this was one of several dozen polynomials which suddenly scrolled over the screen within 2 or 3 seconds):

[code]n: 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171
skew: 1087899.77
c5 [b]28620[/b]
c4 -66150837492
c3 -223841202629128035
c2 149596136381437136431267
c1 151059602958393608146940595699
c0 -63922911265972837908420983912147859
Y0 -153175532962819282953807122
Y1 863922264641669
rlim: 8000000
alim: 6000000
lpbr: 28
lpba: 28
rlambda: 2.55
alambda: 2.55
mfbr: 55
mfba: 55

skew 1087899.77, size 3.393933e-014, alpha -7.240297, combined = 3.791784e-013[/code]

total yield: 23439, q=6005011 (0,06120 sec/rel)

So the second one seems to be ~1.5% better.

Thus at least for large and huge factorizations it might be a good idea to search manually from a5=1 to msieve's lower searching bound (additionally to the default search).

alpha -8.65
 

For a GNFS-140, msieve constructed a somewhat faster polynomial than pol51.

For a GNFS-144, msieve found a poly with [B]alpha -8.65[/B] but it wasn't far the best by E, so the other one was reported (it was also one of the first ones, probably within the first hour of search - out of 86hrs). This poly is 30% slower than the one found by pol51 (I vaguely remember that with pol51 for that number I was oversearching - so it may not be an apple-to-apples comparison).

Here's the record (or is it?) alpha --
[code]N 122334784589234392683295194652612149338189319179115868523072772347572950426690801931827228533310815015647306731512386262336087369965447853346893
# norm 1.807e+21 alpha -8.651144 skew 3886525.11 e 4.843e-14
R0 -3823238955993478880987397298
R1 12332658384071729
A0 -119449348774309735406664634313243332683
A1 -83616546203276391505590316402126
A2 15238476944819293445862257
A3 2880449667385143836
A4 -329607079944
A5 149760
[/code]

Here's the best reported in the end
[code]name: 71117_232
n: 122334784589234392683295194652612149338189319179115868523072772347572950426690801931827228533310815015647306731512386262336087369965447853346893
skew: 953780.82
# norm 9.931e+19 alpha -6.735360 skew 953780.82 e 6.103e-14
Y0: -4121240757474571107437098463
Y1: 12188426568647857
c0: -173269545001174080592966214619225360
c1: 853604845948885102330057755692
c2: 725399799019435768348584
c3: -1324693520369481579
c4: -428130871862
c5: 102900
# Murphy_E 6.103e-14
# M
type: gnfs
rlim: 20000000
alim: 20000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56
rlambda: 2.6
alambda: 2.6
[/code]

Here's pol51's best:
[code]name: 71117_232
n: 122334784589234392683295194652612149338189319179115868523072772347572950426690801931827228533310815015647306731512386262336087369965447853346893
skew: 690006.04
# norm 1.16e+20
c5: 366240
c4: -200755493198
c3: -1264280431194248789
c2: 30690227552865176460280
c1: 116115356677156443273022507812
c0: 1643772806174680731101452821850125
# alpha -6.86
Y1: 12549580773819617
Y0: -3197105916158047746993222154
# Murphy_E 1.41e-11
# M 5734946885270096719071646003056964635381291967622973864385956607094834583149950289638574241818695561052754902888430269917445698295408593930669
type: gnfs
rlim: 20000000
alim: 20000000
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56
rlambda: 2.6
alambda: 2.6
[/code]

The scaling factor at 144-digit size is 265.4, meaning the msieve poly would have an E of 1.62e-11; reports from others indicate that you should not assume the relation rate is better by a factor of 1.62/1.41 though.

I never judge a horse solely by its teeth. I take it for a ride. Of course, "E" estimates are just estimates. When the search was done, I ran both polynoms in a few ranges and got, e.g.:
> gnfs-lasieve4I14e -a *.polyMs -f 20000000 -c 1000 -o t1
total yield: 2618, q=20001001 (0.09375 sec/rel)
> gnfs-lasieve4I14e -a *.poly51 -f 20000000 -c 1000 -o t2
total yield: 2807, q=20001001 (0.07200 sec/rel)
(and I did that for some more polys, and surely for all those that I've ever mentioned above, g121, g140... Of course these are also merely estimates, but the point is that I don't just look at E values...)

I simply think that msieve needed a higher time limit (maybe it ended up not visiting the intended a5 range); that's all. So far, I ran it in default mode. With future optimizations, the optimal time limit may end up being not more but less.

I'm currently searching for a polynomial for 3_527- c160 to compare to the ones we found with Kleinjung's and the CADO programs. Msieve 1.39 is built with x86_64 GMP=1. Command line is
[code]
nohup msieve-1.39 -v -n -np 5466315818570157744600674404470135554420684751405676880272078210385283404043543171940308633417556688973629087522011173645136493977169190093057301775731456787243 >> msieve.stdout 2> msieve.stderr &
[/code]

It prints "warning: skipping corrupt polynomial" to stdout a lot now, 14158 times so far. Is this something to worry about? IIRC Jason mentioned that the poly finder expects numbers not exceeding (or less than?) 160 digits, maybe this one is just a little too big? There is no polynomial in msieve.dat.p yet, after about 19h of running on a Core 2 with 2.13GHz.

Alex

Edit: Ah, posting #2 in this thread says "< 160 digits" so I guess that's why.

I have to fix the stupid integrator, this is a problem trying to rate polynomials that are too large for it.

Also, your 160-digit run is using the 155-digit parameters, so the constraints on polynomal size are much more restrictive than necessary.

[QUOTE=jasonp;150725]
PS: I can't say for sure, but using a larger multiplier should not make a difference to polynomial quality at all. Modern poly selection works much better because choosing a leading rational coefficient larger than one gives you more possibilities than you can ever hope to search in a reasonable time, and using a sieve to find good alpha values improves the alpha much more than using a large multiplier ever could[/QUOTE]

Jason, since msieve now needs small A5 and the multiplier doesn't need to be very smooth to obtain good polynomials, why not choose a multiplier smaller than 60 ? With a multiplier of 12, five times more A5 can be tested and, for large composites, the range of A5 explored won't grow too much.

I can compile msieve with cygwin but this kind of tests (the impact of a multiplier) does require a lot of time...I have tried with a c141 without big differences...for a large C150+, this may be important.

Thanks and regards.

Philippe

[QUOTE=jasonp;150558]
I think that those undocumented fields are only used in stage2 of pol51, in the root sieve. From memory, they're only there to expand or contract the search space where the root sieve looks for polynomials with good root properties.[/QUOTE]
Looking at the source, this is completely wrong. The extra information is fed to the computation of the E score, which looks like it's taken straight out of Murphy's thesis. Everyone should realize that E is not a measure of real-world anything, it's a dimensionless number that is only designed to be sorted, and thus you can only compare two E-values computed with all parameters set identically.

This business of rating polynomials is very tricky, and the next version is going to need a lot of changes to do it better.

Very small question about size-score
 

I realise that the size-score is not a relevant quantity for SNFS jobs, but it still seems a little peculiar that an msieve.fb file

[code]
N 5688016226807831064044758914315660452874822911732021084198059235416884717188698621609682118091029853096510590721423450325168014323277731989012600970545984976786513017985287740035850980703007762825496957935313661984801
A4 1
A3 -1
A2 1
A1 -1
A0 1
R1 -1
R0 49039857307708443467467104868809893875799651909875269632
[/code]

gives

[code]
skew 0.00, size 2.680192e-22, alpha 1.694464, combined = 1.360841e-22[/code]

I suppose this is another robustness test for the integrator, which is clearly tuned for situations with much larger R1/R0.

[SIZE=1]Just some random ruminations (I don't know what to make of them yet, just thinking aloud) -[/SIZE]

I've found that there are some particular SNFS forms where the alpha is always the same and is (by recent obervations possibly adverse) huge positive.

One is a (x^7+-1)/(x+-1) poly - it invariably has the alpha of [B]2.427706[/B].
the other is the (x^13+-1)/(x+-1) converted to a sextic poly (with t=x+1/x)
[code]c0: -1
c1: 3
c2: 6
c3: -4
c4: -5
c5: 1
c6: 1
#alpha [B]3.125762[/B][/code]
Invariably, while doing numbers of this form, you have to sieve deeper/longer than usual (because the LPs go very wide right off the bat, all the way to the pi(2^lpbr), e.g. to over 12,000,000 for a 27-bit project; 2*pi(2^27) ~= 14,343,350, that's an impossible maximum; for comparison, most other projects start converging to a matrix before 10,000,000 large ideals). I am pretty ignorant what alpha really means but most probably it means just that, predicting what will happen with the needed # of relations.

But other than needing a bit more time, with msieve 1.39 - none of these projects ever failed yet. (With 1.38, they have.)

[SIZE=1]My 2 cents after being mangled under the train of thought...[/SIZE]

The integrator is undergoing a lot of work to make estimating the size score more robust.
EDIT: Tom, the scaling for degree 4 is much different from that of degree 5. I used to think that Bernstein's algorithm could compare the scores for any two polynomials, but there is a term in front that is different for different sums of polynomial degrees

Alpha is a measure of how much better a given polynomial is at reducing the average size of sieve values, compared to a random numbers of the same size. The assumption is that values of a given polynomial behave as if they are exp(alpha) times the size of random integers in the same range, because the NFS polynomial will have a different number of roots modulo small primes. Because polynomials with good alpha are quite rare, they have to be searched for. From the code:

[code]
roots of (poly mod p) can be either ordinary or special.
An ordinary root mod p corresponds to exactly one root
mod p^k for all k > 1. Murphy shows that for each ordinary
root of (poly mod p) the contribution to the size of a
random sieve value due to all powers of p is log(p) *
p/(p^2-1).

We compare this to the contribution of powers of p to
the size of a random number. 1 in p random numbers are
divisible by p, 1 in p^2 random numbers are divisible by
p^2, etc. Adding up all of these contributions and summing
the resulting geometric series yields an average contribution
of log(p) / (p-1).

Hence the root score for poly is the sum of the difference
between the contribution of powers of p in sieve values
compared to the contribution to a random number. When there
are k ordinary roots mod p, root_score is the sum of

log(p) * (1/(p-1) - k*p/(p^2-1))

for the first few p, meaning that dividing the small primes
out of sieve values makes their size exp(root_score) times
smaller than dividing the small primes out of a random number.
[/code]