20070509, 17:23  #12 
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 

20070509, 17:41  #13  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
10110110001110_{2} Posts 
Quote:
In my experience, creating and implementing efficient filtering algorithms is far from easy. The simple algorithms are either not very good at filtering or very memory inefficient or both. Most implementations of good algorithms use far too much memory, IMO, and I've spent some time tweaking the CWI filter code to make it run on commonly available machines. Paul Last fiddled with by xilman on 20070509 at 17:42 Reason: Fix typo and trim quoted material 

20070509, 17:49  #14  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
tons of memory. But they take so little TIME that one can afford to do an outofcore implementation using temporary files for storage. 

20070509, 18:44  #15 
(loop (#_fork))
Feb 2006
Cambridge, England
14466_{8} Posts 
What I'm saying is:
Suppose I have sieved against significantly too large a factor base size; say the n(L) primes less than L. What happens if I run the matrixconstruction step as if I had used a smaller factor base, say the n(S) primes less than S? If I sieved allowing two large primes plus the specialQ, I will have lots of relations in which I have two large primes, plus the specialQ, plus one or two primes between S and L; the primes between S and L will seldom be singletons because the number of relations is significantly greater than n(L). I wasn't sure whether the answer would be 'you get a uselessly dense matrix' or 'you don't get a matrix'; doing the runs using the ggnfs matrixbuilding is tending not to give me a matrix at all, but I am losing huge numbers of relations because they're not allowed to have more than three large algebraic primes. I know that, asymptotically, filtering is cheap. I may be confused by the sequence of events when you use the GGNFS suite; that *does* distinguish between factorbase primes and other primes, until it has built a matrix of height the size of the requested factor base, and then 'prunes' that matrix. You're describing filtering, as far as I can tell, as a process which takes a pile of relations and gives you a matrix, without ggnfs/matbuild's twophase structure. I'm using 'factorbase primes' to mean 'primes which label the rows of the matrix'; they have nothing to do with the sieving phase. Last fiddled with by fivemack on 20070509 at 18:58 
20070509, 19:07  #16  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
I can't make sense of it. Do you mean that while filtering, you throw away relations that have (say) 3 or more primes larger than some fixed bound? I can't imagine why such a thing should be necessary. Once you start filtering, a relation is a relation is a relation. The distinction between factor base primes and large primes VANISHES. Why is this so hard? You say "they're not allowed to have more than three large algebraic primes." I ask: why not? Is this a restriction of the particular implementation you are using? If so, then FIX IT. This restriction is not necessary. Indeed, I can't think why it might even be put in filter code. The filtering code SHOULD NOT CARE about the sizes of primes that appear in relations. They should all be treated identically/ Are you complaining about limitations of your software or asking about how to select parameters for good performance?? If GGNFS has unnecessary restrictions, then FIX them. You sound more as if you are complaining about some brain dead restrictions of GGNFS than you are asking about parameterizations. 

20070509, 20:48  #17  
Tribal Bullet
Oct 2004
3^{2}·5·79 Posts 
Quote:
Tom, you don't need a twophase process to construct a matrix; you really can start with a pile of relations and produce a matrix directly. It's useful to have a twophase process because filtering only deals implicitly with big primes, and the matrix can be squeezed down a little after it is formed and you can count the number of empty rows. Whether a factor base exists in the background is a detail that is specific to the implementation, i.e. GGNFS has a relation structure that separates the primes found by sieving from those found by nonsieving means, and it has entries for three of the latter only. Last fiddled with by jasonp on 20070509 at 20:50 

20070509, 21:58  #18 
(loop (#_fork))
Feb 2006
Cambridge, England
1936_{16} Posts 
As far as I can see, GGNFS does not build the matrix from the input relations by filtering according to the model in Cavallar's paper of 2000; it uses an entirely different procedure, in which small primes and large primes are treated separately, and in which all the data structures are set up such that a relation can have no more than three 'large' primes on either side. I suspect what it's doing is closer to the 'structured Gaussian elimination' of the 1990s large sparse linear algebra papers.
The smallprime bound for this procedure is a configurable parameter, usually set to the factorbase bound for the sieving, and I was just wondering what happened if you changed that parameter. I'm afraid we've been talking at cross purposes, and am sorry to have wasted your time; I agree that Cavallar's algorithm does not depend on the size of the primes appearing in the relation. The correct response to ggnfs's limitations is almostsurely to use msieve instead, and msieve's relationset>matrix step is something like Cavallar's algorithm, in which the parameter I was seeking to optimise in ggnfs's implementation doesn't exist. Last fiddled with by fivemack on 20070509 at 22:00 
20070510, 12:14  #19 
(loop (#_fork))
Feb 2006
Cambridge, England
1100100110110_{2} Posts 
Sorry to have bothered you all; the more I look into this, the deeper the deficiencies of ggnfs's relations > matrix stage look. It seems that substantial oversieving causes some very nasty slowdown in the matrixtidying phase, which can't be sensible.
All glory to Jason for implementing something more capable! 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where do I send my PRP primes with large k?  Trilo  Riesel Prime Search  3  20130820 00:32 
48bit large primes!  jasonp  Msieve  24  20100601 19:14 
lots of large primes  Peter Hackman  Factoring  2  20080815 14:26 
NFS with 5 and 6 large primes  jasonp  Factoring  4  20071204 18:32 
What is the use of these large primes  Prime Monster  Lounge  34  20040610 18:12 