20160330, 13:47  #1 
Apr 2014
Marlow, UK
38_{16} Posts 
Nonsieving version of Quadratic Sieve
I've been experimenting with a nonsieving version of the Quadratic Sieve algorithm. To date the performance is nowhere near as good as the basic Quadratic Sieve, let alone SIQS; gathering relations to factor a C80 takes around 14 hours using singlethreaded Haskell over GMP on a standard desktop machine, using the Single Large Prime variation.
However, I am not a proper mathematician, so I am almost certainly missing some obvious algorithmic improvements (I guess I would need a couple of orders of magnitude to make it interesting). In brief, rather than sieving consecutive x values for smooth f(x) values, 'candidate' x values are generated that have a better than average chance of producing smooth f(x) values. Smoothness testing is then carried out using a remainder tree before factoring the values that pass the test, to produce the relations. Would anyone be interested in discussing this with a view to algorithmic refinements? 
20160330, 14:40  #2 
Tribal Bullet
Oct 2004
DED_{16} Posts 
The expected performance of this is worse than that of CFRAC with the same optimizations, since at least in that case the numbers being batch factored are all of size near sqrt(N), whereas with QS the candidates grow in size.
'Early abort' is helpful in both these algorithms, since we expect a lot of small factors in relations but only a few large factors, so it would make sense to do a little sieving and reject sieve values unless only a little of the sieve value is unfactored. In that sense batch cofactorization can be seen as a memoryefficient method for avoiding having to sieve most of the traditional factor base. Making a small sieve run fast is quite easy, using a large sieve much less so. Bernstein wrote around 2004 that it was a myth that sieving was always optimal; needless to say it was a bit controversial :) 
20160330, 15:24  #3  
Apr 2014
Marlow, UK
70_{8} Posts 
Quote:
This is because the candidate x values are chosen such that f(x) has known large(ish) factors from the factor base; sieving would mark these x values, whereas I select them explicitly. Therefore the f(x) can be divided by these factors before smoothness testing and factorisation. Supposing I want f(x) to have factors p1, p2 and p3 from the factor base; f generally has 2 roots modulo each of these, giving 8 xvalues (via the CRT) between 0 and p1*p2*p31 that will give an f(x) with p1, p2 and p3 as factors. I use the least of these xvalues and also the greatest minus p1*p2*p3 (which is negative). This gives smallest (?) abs(x) values, and hence f(x) values, such that f(x) has all 3 factors. I do use earlyexit, and this typically happens when the number of relations reaches the high 80's % of the way to the factor base size (plus margin). 

20160330, 20:57  #4 
Apr 2014
Marlow, UK
70_{8} Posts 

20160330, 23:16  #5 
Tribal Bullet
Oct 2004
5·23·31 Posts 
It's unlikely, but your original description didn't mention that sieving was used, so I also doubt that nonsieving QS would be able to factor a C80 :)

20160331, 06:21  #6  
Apr 2014
Marlow, UK
2^{3}·7 Posts 
Quote:
What needs refinement, I think, is the "candidate generation" stage (see earlier post). For example, at the moment, the "known large factors" of f(x) are from the factor base, but it is also possible to have a factor p^{2}, where p is not in the factor base (using Hensel lifting). So far this doesn't seem to be an improvement, but it gives another dimension for exploration. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve  mickfrancis  Factoring  2  20160506 08:13 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Sieving polynoms in Quadratic Sieve  ThiloHarich  Factoring  13  20090104 18:19 
Mersenneversion of the quadratic sieve  Syd  Math  0  20080919 00:43 
Using p=2 for sieving (Quadratic sieve algorithm)  R1zZ1  Factoring  36  20071102 15:59 