Factoring blocks of numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:19:58Z http://mathoverflow.net/feeds/question/41725 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers 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/41738#41738 Answer by Gerhard Paseman for Factoring blocks of numbers Gerhard Paseman 2010-10-11T02:01:49Z 2010-10-11T02:01:49Z <p>Short answer: I doubt you can do much better than trial factorization. However, for many composite numbers, the run time is often up to the size of the second largest prime factor, so you may actually end up with a better run time than pi(sqrt(N)).</p> <p>Long answer: there are lots of things to try. First is to remove the small factors, of which you know there will be many. Assuming you have them, start removing all factors up to, say q = pi(n), the nth prime. (You can even try it recursively, as e.g. the even members of your sequence are twice a consecutive run of numbers.) You will have left an array of n numbers, many of which are prime or have few factors. If they are less than q^2, then they will be prime or 1, and those numbers can be considered to be completely factored.</p> <p>With the remaining numbers, a fact you know is that each pair is relatively prime. One fun thing to try is to multiply an odd number of them that are about the same size together and then try Fermat's difference of squares method on the result. If you choose few enough of them, you can find a number which has a nontrivial factor in common with one of the numbers in the product.</p> <p>Another thing you can do is take a random selection of primes s in (q, sqrt(N)) and compute N mod s. If the result is between -n and 0, then exactly one of the array has s as a factor. After enough trials of these, you can try high-powered methods on the rest, or even on products of the rest.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.10.10</p> http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers/41831#41831 Answer by tdnoe for Factoring blocks of numbers tdnoe 2010-10-11T20:30:51Z 2010-10-11T20:30:51Z <p>Using a sieve of Eratosthenes approach, it is easy to create a list $S$ of the smallest prime factor of every number less than $N$. Then to factor any $n &lt; N$, we just recursively look up the factors: let $n_1=n$, $f_i = S(n_i)$, and $n_{i+1} = n_i/f_i$. With 4 GB of memory, numbers less than ${10}^9$ are quickly factored. Although this algorithm takes more memory, it is much faster than trial division.</p> http://mathoverflow.net/questions/41725/factoring-blocks-of-numbers/57292#57292 Answer by unknown (google) for Factoring blocks of numbers unknown (google) 2011-03-03T22:08:12Z 2011-03-03T22:08:12Z <p>Daniel Bernstein has a method of finding smooth numbers in batches. See <a href="http://cr.yp.to/papers/sf.pdf" rel="nofollow">http://cr.yp.to/papers/sf.pdf</a>.</p>