mersenneforum.org Don't fear the quartic
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-26, 22:15 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 645210 Posts Don't fear the quartic 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.
 2009-01-27, 05:25 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 25E016 Posts 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...
 2010-05-15, 21:16 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 969610 Posts 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: Code: 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 Code: 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.
 2010-05-16, 03:54 #4 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 100111010012 Posts Code: 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 Code: rlim: 250000000 alim: 40000000 would be fine enough, to be stated up that within a much better way? Thus, with Code: lpbr: 31 lpba: 29 that case/situation is only indeed correct, actually, in the case of a quartic, right then? Last fiddled with by Raman on 2010-05-16 at 03:56
2010-05-16, 07:22   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

25·3·101 Posts

Quote:
 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.

 2010-05-16, 10:44 #6 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 22·1,613 Posts 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.
2011-12-12, 05:08   #7
Walter Nissen

Nov 2006
Terra

2×3×13 Posts
strategy : sextic vs. quintic

Quote:
 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 .

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Soap Box 1 2015-05-23 11:37 R.D. Silverman Factoring 9 2009-02-18 23:24

All times are UTC. The time now is 00:35.

Sat Jan 29 00:35:43 UTC 2022 up 189 days, 19:04, 1 user, load averages: 2.70, 1.92, 1.68