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/.

  • 0
    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.2011-07-30
  • 0
    I'm not sure if I understand you clearly: at what point precisely is the algorithm designed to halt?2011-07-30
  • 0
    @anon: If the algorithm outputs at least on factored integer in **any** of the intervals, it may halt. Yet if its output is in the lower intervals (closer to N), the algorithm is considered better. I'm sorry if I'm not clear; I'll rewrite some parts to better illustrate my goal.2011-07-30
  • 0
    I'm still pretty confused. Factorizing an element of a subinterval is trivially an example of factorizing an element of the original interval, hence the first complete factorization will be in the first interval, and presumably where in this region it succeeds is a matter of chance, so the subintervals are superfluous and the algorithm is basically blind to your desire for numbers closer to $N$, no?2011-07-30
  • 0
    @anon: What I mean is this: Assume that algorithm A is **guaranteed** to generate a factored integer in the first interval, while algorithm B is **guaranteed** to generate a factored integer in the second interval. While algorithm A may occasionally generate a factored integer in the second or lower intervals, there is no guarantee for this. In this regard, algorithm B is "better" than algorithm A, since its guarantee is tighter.2011-07-30
  • 0
    @anon let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/948/discussion-between-sadeq-dousti-and-anon)2011-07-30
  • 1
    I was confused in the same way as anon did, so I edited the question, hoping that it clarifies the question.2011-07-30
  • 0
    @Tsuyoshi: Thanks. The new version seems more clear.2011-07-30
  • 2
    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$?2011-07-31
  • 0
    @Srivatsan: Good question! The motivation is as follows: Let $\ell$ be a **linear** function in n, say $\ell = n/2$. Then, the number $2^{n-1}$ is a fully factored integer in the range $[N-\ell, N]$. So, I needed $\ell$ to be sublinear in n, and I chose $O(\lg n)$.2011-07-31
  • 0
    @Srivatsan: Oops! You're right about the fact that I must have said: for $\ell = N/2$, the number $2^{n−1}$ is a fully factored integer in the range $[N−\ell,N]$. However, I think for $\ell = O(n)$, the prime number theorem somehow guarantees the existence of at least one prime in the range $[N−\ell,N]$, right?2011-07-31
  • 0
    @Srivatsan: Thanks. Can we say anything probabilistic about primes in $[N - O(\log N), N]$? For instance, can we say that for large enough N, there's at least one prime in the mentioned interval with high probability?2011-07-31
  • 3
    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]$.2011-07-31
  • 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