20090126, 22:15  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
14353_{8} 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 difficulty221 fibonacci(1061). Which I think means that we may have been fearing quartics too much; I've been scoring them with a thirtydigit 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^2631. 
20090127, 05:25  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·19·61 Posts 
Sounds about right! A couple of somewhat smaller quartics felt as if the penulty was ~1520. 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 ~215220) 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... 
20100515, 21:16  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×19×61 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 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 30digit 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 testsieving, then one will arrive to conclusions similar to the 0.77 gnfs/snfs ratio. 
20100516, 03:54  #4 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
Code:
rlim: 134000000 alim: 134000000 Rather that Code:
rlim: 250000000 alim: 40000000 Thus, with Code:
lpbr: 31 lpba: 29 Last fiddled with by Raman on 20100516 at 03:56 
20100516, 07:22  #5  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×19×61 Posts 
Quote:
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. 

20100516, 10:44  #6 
(loop (#_fork))
Feb 2006
Cambridge, England
6,379 Posts 
To spoil the fun, these polynomials are matched in the sense that algebraicside sieving of the sextic gives relations at about the same rate per second as rationalside 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 specialQ equal to that prime ...) One observation that I didn't find completely obvious: the time taken to latticesieve with one Q value, in the lowyield 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. 
20111212, 05:08  #7  
Nov 2006
Terra
1001110_{2} Posts 
strategy : sextic vs. quintic
Quote:
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 . 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fear and Loathing on Ebay  LaurV  Soap Box  1  20150523 11:37 
Quartic: Parameters  R.D. Silverman  Factoring  9  20090218 23:24 