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

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]$.


share|cite|improve this question
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: . 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

Your Answer


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

Browse other questions tagged or ask your own question.