-   Factoring (
-   -   Bypass Sieving Stage? (

Sam Kennedy 2016-11-28 15:13

Bypass Sieving Stage?
I had an idea but I thought I would ask here as to not waste time. After the first pass of the sieving algorithm, there will be a set of indices which have accumulated a value higher than some threshold. Would it be possible, knowing the size of the sieving array, and the size of the factor base, to figure out which indices would be over the threshold using the old indices as a starting point? That way sieving could be bypassed and more time spent finding smooths.

I'm guessing if this was possible it would have been implemented already, but even if it's not it would be interesting to understand why not.

jasonp 2016-11-29 02:59

If a bunch of primes p_i divide a particular value in the sieving array, looking for larger sieve values that are also divisible by all the p_i requires hopping down the sieve array in units of (product of p_i). For even moderate size factorizations you need a lot of p_i to land on a single sieve value and their product rapidly exceeds the size of the array. On the other hand, you could force it all to work, and then you would have MPQS :)

All times are UTC. The time now is 20:24.

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