Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
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:… – Gerry Myerson Aug 21 '12 at 4:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.