20080322, 03:06  #1 
Mar 2008
5·11 Posts 
A question on lattice sieving
Hello everyone.
I've got a NFS question. I'm looking at the options for the lattice siever, and noticed the option to sieve over the rational Q's or the algebraic Q's. (This is how I understand it so far. Feel free to correct me if I'm off.) In both of the perl scripts I've seen, as well as looking back at several of the sieve reservation threads on here, I mostly see lattice sieving done on the algebraic side. I was wondering what is the reason for this. Is it that it's more likely for the rational side to be smooth? Or is there some other explanation related to factor base size or other parameter choice? 
20080322, 15:02  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
2·3,191 Posts 
I suppose I usually sieve over algebraic specialQ out of habit; if asked to justify myself, the algebraic side for GNFS jobs is generally much larger than the rational side, and I believe it makes sense to use the specialQ to render effectively smaller the numbers which started off largest, but that's not an answer for why I use a pretty much universally in SNFS cases.
I haven't done the experiments to see how much duplication there is in a case with roughly equalsized rational and algebraic side if you sieve on both sides; it might be sensible as a way to push yields up on SNFS problems with particularly intractable polynomials. 
20080322, 15:50  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10100101100001_{2} Posts 
Quote:
Paul 

20080322, 21:42  #4 
Oct 2006
vomit_frame_pointer
168_{16} Posts 
It seems to be a wash, in my narrow experience
I sieved on the rational side for two SNFS jobs around 180 digits, with nice quintics and reasonable linear polynomials. I noticed no difference in performance.

20080323, 12:46  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Sieve the specialq on the side that has the larger norms. If your SNFS polynomial is wellsuited to the number you're factoring (degree 5 for difficulty ~170, degree 6 for difficulty ~240), the norms on both sides will be very close in size and you can sieve either side (or even both). With lopsided polynomials such as degree 6 for relatively small numbers, or degree 4 for relatively large ones, choosing the specialq on the "right" side has considerable impact on yield. For GNFS, the algebraic side is usually the larger one.
Alex 
20080403, 08:01  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·41·71 Posts 
i am doing a 120 digit gnfs with factMsieve.pl and i have sieved to such a high q 5000000 that sieving is beggining to slow down and i still dont have enought relations i think this is becuse i set it to use gnfslasieve4I12e instead of changing to gnfslasieve4I13e like it suggested
to rectify my mistake can i just stop the script and change it to sieve on the rational side which has an equal size factorbase size if i do that i think that i will have to reduce the q value back to where it started from do i just need to change the job file to make the script change to a lower q, do i have to change gnfs.log or is there anything else tthat i need to change also does anyone know how many duplicates will be found by sieving on both sides the parameters for the factization are: Code:
n: 164662226981356372690290697081101223039515396404303411217671854407296529397066908531205522349477673086175341704695478399 m: c5: 600 c4: 2482582436 c3: 524462069639414 c2: 491993485807382001721 c1: 37023560929310523276836154 c0: 13433130680701991004186914629800 Y1: 2257845554887 Y0: 193951316015185993925111 skew: 478166.41 rlim: 4500000 alim: 4500000 lpbr: 27 lpba: 27 mfbr: 50 mfba: 50 rlambda: 2.4 alambda: 2.4 i have so far found about 4.5 mil relations and i need about 3mil realations getting past msieve's singleton remover currently 272k rels get through it any help would be be much appreciated i have done some tests and it appears that u find more relations in the same time if mfbr and mfba are 54 rather than 50 do i just change that in the job file i have a habit of being over wordy and not making myself understood please ask questions if something i have said confuses u before people start asking what the number is it is RHP585_70 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I'm getting an error when yafu wants to start lattice sieving  Hailstone  YAFU  30  20180523 19:33 
Lattice Sieving Parameters  paul0  Factoring  6  20151120 21:12 
Lattice Sieving  where do I start?  paul0  Factoring  3  20150309 13:54 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
Initialization for lattice sieving  jasonp  Factoring  16  20060112 22:53 