# Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$.

What about shorter intervals? Suppose I wanted to factor all the numbers in $(10^{70},10^{70}+x)$ with $x=10^9$ (more daringly, $10^6$ or $10^3$). Can this be done faster than using general-purpose methods on each number in the range? Is there a good way to decide, at a given size, how long an interval should be to use one method rather than another?

-

## 1 Answer

I think the answer is going to be so heavily implementation-dependent that the best advice is to do a short trial run of both methods and see which is running faster with whatever software and hardware you are using.

-
So there are no clever methods that take advantage of the interval? It's just a matter of finding the switchover point between the two algorithms I mentioned? – Charles Aug 21 '12 at 3:59
I doubt it. Knowing the factorization of $n$ tells you very little about the factorization of $n+1$; knowing the factorizations of $n,n+1,\dots,n+k$ tells you very little about the factorization of $n+k+1$. I think there was a question about this on MathOverflow. – Gerry Myerson Aug 21 '12 at 4:30
Not identical but related: mathoverflow.net/questions/72076/… – Gerry Myerson Aug 21 '12 at 4:37