Current Work & A Query

[bsquared]

Originally Posted by bsquared

I had not considered octic polynomials... can msieve deal with them? Or the ggnfs postprocessing suite? I don't have any other tools at my disposal for postprocessing.

the ggnfs lattice siever didn't like the octic either... simply didn't recognize the c7 or c8 lines.

n: 17046484339439502390787014663843382603841990311536588019427381788315112645544913528357093997566704677217496355462170676223202258500459624221675999642483043420478565738287873667689291
skew: 1 
c8: 1
c7: -1
c6: -7
c5: 6
c4: 15
c3: -10 
c2: -10 
c1: 4
c0: 1
Y1: 140737488355328 
Y0: -19807040628566084398385987585
rlim: 85000000 
alim: 85000000 
lpbr: 30
lpba: 30 
mfbr: 60 
mfba: 60 
rlambda: 2.6 
alambda: 2.6

btw, I think the poly coefficients are correct... at least, they make the equation f(b+1/b)*b^8 - (b^17+1)/(b+1) = 0 when f(x) = c8*x^8 + ... + c1*x + c0

[jasonp]

Originally Posted by bsquared

I had not considered octic polynomials... can msieve deal with them? Or the ggnfs postprocessing suite? I don't have any other tools at my disposal for postprocessing.

Msieve can only deal with degree 6 or less; if you want to recompile the source, just increment MAX_POLY_DEGREE in gnfs/gnfs.h

While this could make the library (and its line siever) work, it doesn't make degree 8 a good idea.

[bsquared]

Originally Posted by R.D. Silverman

But it would be an interesting experiment.....

Does your lattice siever handle octic's? If so, I can try to get it built on my system and run a few sieve experiments. Let me know if it can and if you're willing and I can PM you contact info.

[R.D. Silverman]

Originally Posted by bsquared

Does your lattice siever handle octic's? If so, I can try to get it built on my system and run a few sieve experiments. Let me know if it can and if you're willing and I can PM you contact info.

I have to change a defined parameter and recompile.

However, my suggestion was a joke of sorts.... An octic will be quite
slow; the norms will be very unbalanced.

[fivemack]

Yes, it will be a long time before octics make sense.

Pick a Q; the basis of the lattice will have entries around \sqrt Q; with gnfs-lasieve4I14e, the search region is I think 2^15 x 2^14, so A and B will be around 2^13 \sqrt Q.

So the octic polynomial will have values around 2^104 Q^4 ( = (2^13 \sqrt Q)^8), the linear around 2^94 \sqrt Q. Lattice-sieve on the algebraic side, so you get a free factor Q; Q ~ 2^26 in this case, so algebraic things are ~182 bits and linear ~107 bits. Say large-prime bound is 2^31; yield estimate is (182/31)^(-182/31) * (107/31)^(-107/31) or 4e-7. Not quite as disastrous as I'd have feared.

For a sextic, the polynomial values are around 2^78 Q^3, the linear around 2^134 \sqrt Q. Again Q ~ 2^26, algebraic things are around 130 bits after taking out the free factor Q, rational around 147 bits, yield estimate 1.53e-6, or 1.44e-6 if you sieve on the rational side.

(that argument suggests the algebraic side is very slightly better, but it'll be lost in the noise. The problem with comparing rational and algebraic sides over short intervals is that the number of usable Qs can fluctuate quite a lot. In 85M..85M+1k, you have 63 valid rational-side Q and 44 valid algebraic-side Q, so you'd expect a larger yield from the rational side).

? k=0;forprime(p=85e6,85e6+1000,k=k+1);print(k)
63
? k=0;forprime(p=85e6,85e6+1000,k=k+length(polrootsmod(2*x^6+1,p)));print(k)
44

[fivemack]

Once you've got a million relations, count (uniq -d or similar) how many duplicates you have; I know the coupon-collecting model is invalid because there are several different kinds of coupons, but if you believe the coupon-collectors then you'd expect 10,000 times as many duplicates from the full 10^8 relations as you find among the first million - so if you have much over 2500 duplicates from a million, you might want to use a larger search region.

[bsquared]

This is great, I'm learning a lot already and I've hardly even started yet. Thanks Fivemack for the yield estimation example - I understand section 2 of Silverman's "Optimal parameterization of SNFS" a bit better now.

I've done some more yield estimates and I now think algebraic side sieving will be better, but the difference is hardly noticable. In either case, I think I'll need a range of 120M rather than 100M.

5^293 - 3^293 is in linear algebra now, so I've starting sieving for this project. I'll post updates here.

[henryzz]

you could try both algebraic and rational sieving
it worked quite well for me it didnt appear that there were many duplicates caused by that

[bsquared]

After sieving from 75M to 112M on the algebraic side, I've yielded ~32M relations with about 5.5% duplication (32.494M rels, 30.725 unique). So my initial optimistic projection is actually looking realistic.

I'll do at least a few million q of overlapping rational side sieving at some point, if for no other reason than that I'm curious about the duplication percentage.

[xilman]

Originally Posted by bsquared

After sieving from 75M to 112M on the algebraic side, I've yielded ~32M relations with about 5.5% duplication (32.494M rels, 30.725 unique). So my initial optimistic projection is actually looking realistic.

I'll do at least a few million q of overlapping rational side sieving at some point, if for no other reason than that I'm curious about the duplication percentage.

Perhaps so. If so, I'll be somewhat surprised. Consider a birthday paradox model in which the number of dups grows as O(sqrt N).

We'll doubtless find out in due course.


Paul

[bsquared]

Originally Posted by jasonp

Msieve can only deal with degree 6 or less; if you want to recompile the source, just increment MAX_POLY_DEGREE in gnfs/gnfs.h

While this could make the library (and its line siever) work, it doesn't make degree 8 a good idea.

In polyutil.c, I see this code block

 
#if MAX_POLY_DEGREE > 6
#error "polynomial degree > 6 not supported"
#endif

so simply modifing the #define in gnfs.h produces the above error. I also note that in get_polyval(...), cases for poly degree > 6 do not exist. I'm pretty sure it would be non-trivial to add the necessary code to make the library work with degree > 6, and of course I am not trying to tell you to do so... just FYI.