7
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ I'm not sure that this is inappropriate here, but you should definitely post this on stackoverflow.com as well. $\endgroup$
    – Eric Tressler
    Commented Oct 11, 2010 at 1:09
  • 6
    $\begingroup$ I vote for appropriate. $\endgroup$
    – Charles
    Commented Oct 11, 2010 at 1:31
  • $\begingroup$ It's not clear to me what ranges you are considering. If $N$ is around $10^{30}$, say, then you are not going to compute and store all the primes up to $\sqrt N$. Then again, if $N$ is around $10^{30}$, and $n$ is near $\sqrt N$, I can hardly see holding, much less factoring, all the numbers from $N$ to $N+n$. So, what do you really want to do? $\endgroup$
    – Gerry Myerson
    Commented Oct 11, 2010 at 2:21
  • 2
    $\begingroup$ OK, then I think Gerhard has the right idea. Remove all prime factors up to some bound $Q$, test what's left for pseudo-primality with some quick test. Apply a rigorous primality test to the ones that pass the test, and a factorization method like Pollard rho or Pollard $p-1$ to the ones that don't. Details on how some of these tests run can be found in Riesel, Prime Numbers and Computer Methods for Factorization. $\endgroup$
    – Gerry Myerson
    Commented Oct 11, 2010 at 5:51
  • 1
    $\begingroup$ Just noting that Eric's original comment says "inappropriate" and not "appropriate," expressing what I read as genuine unsureness (so I don't think Pete actually disagrees). I think the suggestion that it be cross-listed on SO is a fairly reasonable one. $\endgroup$
    – Cam McLeman
    Commented Oct 11, 2010 at 20:48

3 Answers 3

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .