How to identify SNFS candidates and factor them?

[charybdis]

Nicely done!

Originally Posted by bsquared

At the risk of increasing confusion, I ran this through yafu's poly select and it slightly prefers the other degree 5:

Yes:

Originally Posted by charybdis

You could also represent this number as 8*1281979*2^520+1, giving c5 = 10255832, c0 = 1, Y1 = 1, Y0 = -2^104. This choice of polynomial might even be slightly faster than yours; at least it has a higher E-score. For some numbers there will be even more polynomials to choose between: this will often be the case when near the crossover between degree 5 and degree 6, for instance (and here we have to test-sieve, as E-scores from different degrees are not comparable).

I suggested sieving on the rational side but YAFU just about prefers algebraic side for this polynomial - for a larger number this would call for test-sieving. k*2^n+1 would be a rational side job for the usual small values of k (e.g. 1) but as k gets bigger so do the algebraic norms.

[VBCurtis]

Originally Posted by bur

The factorization completed successfully!

Slightly less than 2 hours instead of 3 days for a GNFS c149.

It went back to sieving a couple of times due to me setting the rels_wanted too low as charybdis mentioned.

I think you'll fly through all the composites under 2^600 for your chosen k-value rather quickly now. :)

I'd try making lim0 and lim1 the same (use the larger of the two from my C120 file). That'll require a few more relations, maybe 10% more, but the job should go faster. About every 30 bits of exponent increase, step to the next-bigger params file for lim/lpb choices.

[bur]

I updated Yafu, poly generation works, it's even doing test sieving on two polys.

I'd try making lim0 and lim1 the same (use the larger of the two from my C120 file). That'll require a few more relations, maybe 10% more, but the job should go faster. About every 30 bits of exponent increase, step to the next-bigger params file for lim/lpb choices.

Thanks for the advise. So I should just use the lim/lpb from the next params file but otherwise still use the params.c120?


And out of curiosity, what is the reasoning behing making lim0 and lim1 the same, why does it save time?

[VBCurtis]

When the norms of the two sides are quite different in size, CADO is more efficient when making the side with the larger norm also have a larger lim.
Since your job has anorm and rnorm very similar in size, there isn't an obvious reason to make the lim's different in size.

I'd change entirely to params.c125 when you get 30 bits bigger than you are now.

SNFS jobs double in difficulty about every 9 digits, while CADO-GNFS jobs double in difficulty about every 5 digits. With YAFU giving you polynomials, you'll be able to get quite far in your factoring sequence.

[bur]

I tried 2^528 with yafu settings and the sieving had an ETA of about 3 h if I chose tasks.sieve.sqside = 1 as per EdH's guide. I switched to tasks.sieve.sqside = 0 and ETA changed to 1 h. I also changed lim0/1 to 4500000 instead of yafu's 6100000 (yes, never change more than one parameter when testing), but I guess the sqside=0 is the big impact?

Would it be advisable to generally use yafu's settings but with tasks.sieve.sqside = 0?

[VBCurtis]

It's advisable to experiment a lot, as you are doing. That's how we all learned!
SNFS jobs have fewer "do it this way" guidelines, more job-specific settings.
I'm surprised there is a factor-of-2 difference in speed for sieving the other side- the norms suggest the decision should be a close call.

[swellman]

There is a lot of empirical data on Kamada’s site that you may find helpful. It has an accumulation of data as reported over the years. Some cases are certainly non-optimal but all are definitely “what worked”.

There are also the log files spread throughout the various NFS@Home sievers. Start with lasieved - it performs sieving for the smallest factoring jobs. Keep in mind NFS@Home uses a BOINC wrapper so there are some inefficiencies baked in, such as the target number of relations being artificially elevated to compensate for a percentage of “junk” relations received back by the servers from the volunteer workers.

But experimentation is always the best way.

[charybdis]

Originally Posted by bur

I tried 2^528 with yafu settings and the sieving had an ETA of about 3 h if I chose tasks.sieve.sqside = 1 as per EdH's guide. I switched to tasks.sieve.sqside = 0 and ETA changed to 1 h. I also changed lim0/1 to 4500000 instead of yafu's 6100000 (yes, never change more than one parameter when testing), but I guess the sqside=0 is the big impact?

Would it be advisable to generally use yafu's settings but with tasks.sieve.sqside = 0?

I don't know how you got such a huge difference in the ETAs; CADO can spit out some suspect values early on in the job, and I bet that if you let these jobs run to completion the running times would be much closer. I did some test-sieving on this number with YAFU's choice of polynomial and params, and tasks.sieve.sqside = 0, ie rational side sieving, is definitely faster - but not by anywhere near that much. The advantage is larger at smaller Q values and I reckon it would amount to ~15% over the whole job.

I calculated the norms for a few relations around Q=2M, and typical values are something like 10^36 for the algebraic norm and 10^39 for the rational norm. This is consistent with a small advantage for rational-side sieving. YAFU's estimates weren't too far off, but it overestimated the algebraic norm and so it chose the algebraic side for sieving.

I'd say keep on using tasks.sieve.sqside = 0 for these jobs, as it's likely that YAFU is systematically overestimating the algebraic norm. The advantage for the rational side should grow as the numbers get larger, until you switch to degree 6 at which point the algebraic side may be worth considering again.

@bsquared, if you're reading this - maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?

[bur]

maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?

I think it does that, when yafu is test-sieving I'm quite sure I saw it doing a test for algebraic side.


Maybe the large difference I found was caused by various factors, cado vs msieve, optimized vbcurtis parameters etc.


What also brings a nice boost is starting at much lower q-values, instead of 60000 I now start at 10000 which for some numbers had 50 rels/q while at the final q it was about 15 or 16. Maybe it's advisable to go even lower.

[charybdis]

Originally Posted by bur

I think it does that, when yafu is test-sieving I'm quite sure I saw it doing a test for algebraic side.

On this number, YAFU test-sieves three polynomials. For each one, it decides which side it thinks is fastest and tests only that side. I'm suggesting that it should also test algebraic vs rational for the same polynomial.

What also brings a nice boost is starting at much lower q-values, instead of 60000 I now start at 10000 which for some numbers had 50 rels/q while at the final q it was about 15 or 16. Maybe it's advisable to go even lower.

Starting at very small q may look faster, but most of those relations will end up being duplicates, and you'll end up needing more raw relations to build a matrix. I did some testing on numbers in the c175-180 range last year which showed that starting at very low q-values is slower despite the increased yield; Curtis's rule of thumb is to aim for a qmin-to-qmax ratio of 7 to 8. I think Curtis has some updated param files for small numbers which he hasn't released yet, and I would guess that the new c120 file will have a larger qmin than 60000.

[bsquared]

Originally Posted by charybdis

I calculated the norms for a few relations around Q=2M, and typical values are something like 10^36 for the algebraic norm and 10^39 for the rational norm. This is consistent with a small advantage for rational-side sieving. YAFU's estimates weren't too far off, but it overestimated the algebraic norm and so it chose the algebraic side for sieving.

I use the following as average a,b values for norm estimates (I got these from you a few months back):
a = sqrt((double)(1ULL << (2 * I - 1)) * 1000000.0 * poly->poly->skew);
b = sqrt((double)(1ULL << (2 * I - 1)) * 1000000.0 / poly->poly->skew);

But don't take into account root properties and obviously the Q is static. If there is a better way that is nearly as simple that'd be great.

But the reason it is choosing algebraic side is that yafu is biased that way on purpose. The rational norms need to be about 5 orders of magnitude larger on the rational side before it will choose to sieve there. Can't remember why I did that... I think it's because for gnfs jobs it is usually the case where alg side is better, even when the norms are slighter higher on the rational side.

Originally Posted by charybdis

@bsquared, if you're reading this - maybe worth getting YAFU to test-sieve algebraic vs rational when the estimated norms are close together?

Yes, another good idea. Should be fairly straightforward to implement.