View Single Post
Old 2016-03-30, 13:47   #1
Apr 2014
Marlow, UK

23·7 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