Factoring blocks of numbers - MathOverflow

Factoring blocks of numbers

2010-10-11T00:10:46Z

Asked this question in a different formulation in cstheory, got some pointers, but no definitive answer ... maybe someone here knows.

Suppose I need to compute the factorization of a block of consecutive numbers N, N+1, ... N+n.

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).

If $n>\sqrt{N}$, I can compute primes up to $\sqrt{N}$ and then factorize the whole block directly in O(n) time.

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}$.

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.

Answer by Gerhard Paseman for Factoring blocks of numbers

2010-10-11T02:01:49Z

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)).

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.

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.

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.

Gerhard "Ask Me About System Design" Paseman, 2010.10.10

Answer by tdnoe for Factoring blocks of numbers

2010-10-11T20:30:51Z

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 < 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.

Answer by unknown (google) for Factoring blocks of numbers

2011-03-03T22:08:12Z

Daniel Bernstein has a method of finding smooth numbers in batches. See http://cr.yp.to/papers/sf.pdf.