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?


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.

  • $\begingroup$ 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? $\endgroup$ – Charles Aug 21 '12 at 3:59
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Aug 21 '12 at 4:30
  • $\begingroup$ Not identical but related: mathoverflow.net/questions/72076/… $\endgroup$ – Gerry Myerson Aug 21 '12 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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