mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-03-30, 13:47   #1
mickfrancis
 
Apr 2014
Marlow, UK

708 Posts
Default Non-sieving version of Quadratic Sieve

I've been experimenting with a non-sieving 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 single-threaded 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?
mickfrancis is offline   Reply With Quote
Old 2016-03-30, 14:40   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

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 memory-efficient 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 :)
jasonp is offline   Reply With Quote
Old 2016-03-30, 15:24   #3
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by jasonp View Post
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 memory-efficient 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 :)
Thanks Jason. Interestingly, because of the way the candidate x values are chosen, subsequent factoring is on values less than sqrt(n), sometimes by a factor of more than 10. Also, the values being factored remain the same order of magnitude throughout.

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 x-values (via the CRT) between 0 and p1*p2*p3-1 that will give an f(x) with p1, p2 and p3 as factors. I use the least of these x-values 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 early-exit, and this typically happens when the number of relations reaches the high 80's % of the way to the factor base size (plus margin).
mickfrancis is offline   Reply With Quote
Old 2016-03-30, 20:57   #4
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by jasonp View Post
The expected performance of this is worse than that of CFRAC with the same optimizations
Can CFRAC really factor a C80 (in less than 14 hours)?
mickfrancis is offline   Reply With Quote
Old 2016-03-30, 23:16   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,163 Posts
Default

It's unlikely, but your original description didn't mention that sieving was used, so I also doubt that non-sieving QS would be able to factor a C80 :)
jasonp is offline   Reply With Quote
Old 2016-03-31, 06:21   #6
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by jasonp View Post
It's unlikely, but your original description didn't mention that sieving was used, so I also doubt that non-sieving QS would be able to factor a C80 :)
Ah, well, this is my point you see :) I have a non-sieving implementation, in Haskell, that does generate enough relations to factor a C80 in 14 hours. As far as I can tell, this is currently the fastest non-sieving, congruence-based method for numbers of this size (a claim I make with some trepidation...). Of the non-congruence-based algorithms, ECM is faster, I think, even when both factors are of similar magnitude, but then rather a lot of R&D has gone into that!

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 p2, 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.
mickfrancis is offline   Reply With Quote
Reply

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 2016-05-06 08:13
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Sieving polynoms in Quadratic Sieve ThiloHarich Factoring 13 2009-01-04 18:19
Mersenne-version of the quadratic sieve Syd Math 0 2008-09-19 00:43
Using p=2 for sieving (Quadratic sieve algorithm) R1zZ1 Factoring 36 2007-11-02 15:59

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

Sun Nov 29 02:28:36 UTC 2020 up 79 days, 23:39, 3 users, load averages: 1.34, 1.19, 1.19

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.