Go Back > Factoring Projects > Factoring

Thread Tools
Old 2016-11-28, 15:13   #1
Sam Kennedy
Sam Kennedy's Avatar
Oct 2012

10100102 Posts
Default 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.
Sam Kennedy is offline   Reply With Quote
Old 2016-11-29, 02:59   #2
Tribal Bullet
jasonp's Avatar
Oct 2004

2×3×19×31 Posts

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 :)
jasonp is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
How to use prime95 for stage 1 & GMP-ECM for stage 2 Prime95 Lone Mersenne Hunters 111 2015-06-13 03:18
How do you bypass YouTube ads? Stargate38 Lounge 16 2013-02-20 22:46
Stage 1 with mprime/prime95, stage 2 with GMP-ECM D. B. Staple Factoring 2 2007-12-14 00:21
bypass self-test E_tron Software 4 2005-07-13 07:37
Stage 1 and stage 2 tests missing Matthias C. Noc PrimeNet 5 2004-08-25 15:42

All times are UTC. The time now is 23:32.

Fri Jan 22 23:32:38 UTC 2021 up 50 days, 19:43, 0 users, load averages: 2.61, 2.51, 2.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.