Don't fear the quartic

[fivemack]

2^860+1 (difficulty 207.1) took me 2500hrs sieving + 90hrs x 4 cores linalg on a 5.8M matrix. Sieving time was about the same as 10^259+1 (difficulty 222), and the matrix was a bit smaller. The matrix is about twice as many rows as for 10^309+1 (difficulty 206).

2^925+1 (difficulty 222.8) took, I'd estimate, 15000 hrs sieving, followed by 200hrs x 4 cores linalg on an 8.3M matrix. So that's intermediate between 2^1188+1 and 3^512+1, so say about difficulty 240, and the matrix just slightly bigger than for 2^1188+1, only about 25% bigger than the difficulty-221 fibonacci(1061).

Which I think means that we may have been fearing quartics too much; I've been scoring them with a thirty-digit penalty to the difficulty, and it looks as if the right penalty is under 10% ... so the nice round number 2^1000+1 would probably be easier than 10^263-1.

[Batalov]

Sounds about right! A couple of somewhat smaller quartics felt as if the penulty was ~15-20. In August, I, too, have briefly looked at the sieving speed of 2^860+1 after doing 7^384+1 (which was a sextic, ~216), and had the same feeling -- it sieved twice slower (i.e. as if ~9 digits), so it felt like at most as a ~225 instead of its difficulty 207. That's for sieving, but the reward is awaiting at the matrix stage. Raman, notably, finished his 10,375- (a ~200 which probably felt like ~215-220) and the smaller matrix helped (his comp had just enough memory for it; good!).

There are some 2,nnnnM/L quartics available for those who want (not just multiples of 5)... No quartics in homogeneous Cunninghams at this time (the last one was 12+7,200), but there will be plenty after the imminent extension...

[Batalov]

As the remaining quartics grow larger and larger, an interesting rephrased question for me was "when shall we start fearing the quartics?"

Here's a deliberate illustration. Consider an upcoming quartic for the 5,415+ (nominal SNFS difficulty 232) and a finished factorization project (3,551-, SNFS diff.263). The polynomials with matched parameters:

name: 3m551
n: 1780104948926877638194689107156992129997997066100980724222023061066967519543793454850617654535408787953821926319415504722159728336814161357035239278917978564247569709418630128246820485195054605881292497405097702889921685079374904597048447
c6: 1
c0: -3
Y1: 1
Y0: -78551672112789411833022577315290546060373041
skew: 1.20
type: snfs
rlim: 134000000
alim: 134000000
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
rlambda: 2.6
alambda: 2.6

name: 5p415
n: 409070648357903876177895795121676558808515790800199330391475022633084608638318069844299258901345227277398314550159052254251424043657457443453213674736966457975676435972876537687720951817693078563918161701
Y0: -10339757656912845935892608650874535669572651386260986328125
Y1: 1
c0: 1
c1: -1
c2: 1
c3: -1
c4: 1
skew: 1
type: snfs
lpbr: 31
lpba: 31
mfbr: 62
mfba: 62
rlim: 134000000
alim: 134000000
rlambda: 2.6
alambda: 2.6

Test-sieve them in various 2000 ranges, e.g. with 15e. (The parameters are matched to make it a meaningful comparison.)

I suggest that factoring either of these will take roughly the same sieving time; the quartic can be somewhat optimized with slanted limits and inevitable -r sieving, the other one can be done on either side (or both).

This is not yet the fear zone, but still a reason for considering some wanted 30-digit larger numbers as opposed to smaller unwanted quartics. Surely, 3m551 was done and 5p415 can be done with the same resources. The impractical zone is probably another 10 digits higher.

Note that the gnfs/snfs decision boundary for quartics like these is about at 0.77 gnfs/snfs ratio. Alternatively, one can estimate Murphy E values and compare them; because quartics sieve 3 times better on rational side, one can adjust the quartics' E by a factor of 1.5 and proceed with E comparisons as usual, followed by test-sieving, then one will arrive to conclusions similar to the 0.77 gnfs/snfs ratio.

[Raman]

rlim: 134000000
alim: 134000000

What is this? For a quartic, don't you want to have much lower algebraic factor base limits, and then with that somewhat higher rational factor base bounds/sizes?

Rather that

rlim: 250000000
alim: 40000000

would be fine enough, to be stated up that within a much better way?

Thus, with

lpbr: 31
lpba: 29

that case/situation is only indeed correct, actually, in the case of a quartic, right then?

[Batalov]

Originally Posted by Batalov

... The polynomials with matched parameters:

... (The parameters are matched to make it a meaningful comparison.)

... the quartic can be somewhat optimized with slanted limits and inevitable -r sieving, ...

I seem to have failed to mention that the parameters were matched to make it a meaningful comparison.

Either that, or you didn't read the message.

To compare two polynomials (usually for the same number):
1) set parameters to anything you like, but put the same set of parameters in both polynomial files,
2) sieve with any siever you like, but enough to be statistically significant,
3) compare,
4) ..........
5) PROFIT!

I merely extended this pattern to two different numbers.

[fivemack]

To spoil the fun, these polynomials are matched in the sense that algebraic-side sieving of the sextic gives relations at about the same rate per second as rational-side sieving of the quartic. I've tried experimenting with skewed bounds and can't make the quartic more than 10% or so faster.

(I still haven't figured out a decent way of estimating duplication from subsamples: the use of precisely two large primes means that it is not true that, if a prime appears in a relation, that relation will be found by sieving with special-Q equal to that prime ...)

One observation that I didn't find completely obvious: the time taken to lattice-sieve with one Q value, in the low-yield case where we usually are, is pretty much constant and not very correlated with yield, so when doing strategy comparisons it is better to measure that rather than the total_time / total_relations figure which is rendered noisy by both the distribution of primes and the yield issues.

[Walter Nissen]

Originally Posted by fivemack

One observation that I didn't find completely obvious: the time taken to lattice-sieve with one Q value, in the low-yield case where we usually are, is pretty much constant and not very correlated with yield, so when doing strategy comparisons it is better to measure that rather than the total_time / total_relations figure which is rendered noisy by both the distribution of primes and the yield issues.

NFS having so many moving parts , I haven't found too much completely
obvious .
Would you please specify the antecedent of the pronoun in "it is better to measure that" ?
By "total_time / total_relations" do you refer to some aggregation of
the sec/rel values which 1xe places at the end of lines such as :
"total yield: 32669, q=2600011 (0.26413 sec/rel)" ?
I'm looking at np ( 96 ) = 96^96 + 97^97 , an s193 .
Should I dismiss the sextic without testing , even though the coeffs are
smaller than the quintic ?
I think the number of raw relations for lp = 25 , 26 , 27 , 28 is
supposed to be something like 3 M , 6 M , 11 M , 22 M , though using
lp = 26 for np ( 91 ) , an s181 , ggnfs required 9.5 M .
If I'm going to test , is the number required for a sextic the same as for
a quintic ?
Thanks .