3
$\begingroup$

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 Answers 1

1

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.

  • 0
    Not identical but related: http://mathoverflow.net/questions/72076/factoring-some-integer-in-the-given-interval2012-08-21