# Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval $[N - O(\log N), N]$?

Note that the running time of the algorithm is measured in $|N| = O(\log N)$.

Extra: The idea is to generate a factored integer as closed to N as possible. So, it is more desirable to have an efficient algorithm which, for large enough N, its output is a factored integer in the interval $[N - O(\log\log N), N]$.

Cross-posted: http://mathoverflow.net/questions/72076/.

-
At some point, $\lg\cdots\lg n<1$, meaning the algorithm eventually has to factor $N$. This is at least as hard as efficiently factorizing an arbitrary large number. –  anon Jul 30 '11 at 11:08
I was confused in the same way as anon did, so I edited the question, hoping that it clarifies the question. –  Tsuyoshi Ito Jul 30 '11 at 17:57
I understand it is desirable to produce a fully factorized number in the range $[N-\ell; N]$ with $\ell$ as small as possible. But is there a motivation behind the specific starting choice of $\ell = \log n$? Can you solve the problem with a much larger $\ell$? –  Srivatsan Jul 31 '11 at 2:12
I want to emphasize that conditioned on Cramér's conjecture on the worst-case prime gaps, the problem can be easily solved with an interval of length $O(\log N)^2$: just output a prime in the interval $[N-O(\log N)^2; N]$. –  Srivatsan Jul 31 '11 at 5:47
Inspired by this problem, @Sadeq and I made up a question: math.stackexchange.com/questions/54719 . It is about the gaps in what I call "almost polylog-smooth" numbers, which is an infinite family of integers that can be easily factored. –  Srivatsan Jul 31 '11 at 13:00