most recent 30 from http://mathoverflow.net 2013-05-18T21:56:52Z http://mathoverflow.net/feeds/user/9932 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers Nameless 2010-10-11T00:10:46Z 2011-03-03T22:08:12Z

<p>Asked this question in a different formulation in cstheory, got some pointers, but no definitive answer ... maybe someone here knows.</p> <p>Suppose I need to compute the factorization of a block of consecutive numbers N, N+1, ... N+n. </p> <p>As far as I understand, there are two extreme cases. On one hand, if n is very small, I can use algorithms for isolated numbers such as the quadratic sieve. Those are very nice because they make factorizations of 100-digit numbers tractable, but they have limited usefulness for smaller N's (for example, the complexity of the quadratic sieve for N=10^15 comes out to 60,000 operations).</p> <p>If $n>\sqrt{N}$, I can compute primes up to $\sqrt{N}$ and then factorize the whole block directly in O(n) time.</p> <p>In between these two extremes, isolated integer factorization methods are slow due to a big fat constant, and direct factorization is slow because it has a minimum running time of $O(\pi(\sqrt{N})) = \sqrt{N} / \ln \sqrt{N}$. </p> <p>Is there any algorithm that will get me a better running time in this region? We can assume that I have all the prime numbers up to $\sqrt{N}$ computed and stored so the time to compute them does not have to be included.</p>

http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers Nameless 2010-10-11T04:21:54Z 2010-10-11T04:21:54Z

Gerry: I am considering N on the order of 10^18 .. 10^20 and n small enough to keep memory requirements within CPU cache of a modern processor (so, under 10^7).