7
$\begingroup$

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: https://mathoverflow.net/questions/72076/.

  • 2
    Inspired by this problem, @Sadeq and I made up a question: http://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.2011-07-31

0 Answers 0