mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-03-22, 03:06   #1
joral
 
joral's Avatar
 
Mar 2008

5×11 Posts
Default 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?
joral is offline   Reply With Quote
Old 2008-03-22, 15:02   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23×797 Posts
Default

I suppose I usually sieve over algebraic special-Q 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 special-Q 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 equal-sized 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.
fivemack is offline   Reply With Quote
Old 2008-03-22, 15:50   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1039410 Posts
Default

Quote:
Originally Posted by fivemack View Post
I suppose I usually sieve over algebraic special-Q 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 special-Q 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 equal-sized 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.
I generally sieve with special-Q on the side which has the typically larger norms. As the side with the special-q is guaranteed to be divisible by q, the remaining portion required to be smooth is correspondingly reduced.

Paul
xilman is offline   Reply With Quote
Old 2008-03-22, 21:42   #4
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

1011010002 Posts
Default 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.
FactorEyes is offline   Reply With Quote
Old 2008-03-23, 12:46   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Sieve the special-q on the side that has the larger norms. If your SNFS polynomial is well-suited 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 special-q on the "right" side has considerable impact on yield. For GNFS, the algebraic side is usually the larger one.

Alex
akruppa is offline   Reply With Quote
Old 2008-04-03, 08:01   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

11×523 Posts
Default

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 gnfs-lasieve4I12e instead of changing to gnfs-lasieve4I13e 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
should i now change to gnfs-lasieve4I13e or will that not be necessary to find enough relations
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
henryzz is offline   Reply With Quote
Reply

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 2018-05-23 19:33
Lattice Sieving Parameters paul0 Factoring 6 2015-11-20 21:12
Lattice Sieving - where do I start? paul0 Factoring 3 2015-03-09 13:54
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
Initialization for lattice sieving jasonp Factoring 16 2006-01-12 22:53

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

Thu Dec 3 02:00:05 UTC 2020 up 83 days, 23:11, 1 user, load averages: 2.30, 2.40, 2.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.