Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

I wrote a Python Function which assumed that there would be some integer in the interval

[N, N+log2(N)] which was essentially factor-able by small integers.

My program proved that in general this is not the case.

Kermit Rose

share|cite|improve this answer
But as you know a number may be easy to factor even if it is not a product of small primes. – Gerry Myerson Jun 19 '12 at 3:45

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.