# Factoring some integer in the given interval

I'm posting this question here (rather than on CSTheory) since it seems to require much more knowledge about number theory than algorithms.

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

Cross-posted http://math.stackexchange.com/questions/54580.

-
I'm just thinking aloud here, rather than trying to impart wisdom. But I was wondering if it'd be useful to start off by doing the quadratic sieve for all the integers in an interval simultaneously, and homing in on good-quality candidates. After all, for any small prime $p$, the numbers $N-k,\ldots,N$ will be quadratic residues mod $p$ approximately half the time. So if we're looking for sources of smooth numbers, we can quickly choose to work with only those $N-i$ which are quadratic residues mod several small primes. – James Cranch Aug 4 '11 at 14:48
– Kaveh Aug 4 '11 at 15:15

I think Felipe Voloch has the right sense about the problem: you should expect to encounter a prime or a number which is a small number times a prime. Since you suggested probabilistic and did not mention that you wanted ONLY the desired number output, here is a start on your desired program.

Pick a desired small bound B, which will be the largest of the primes to be sieved out. Make B compatible with the desired running time of your eventual program, but I like Felipe's suggestion of $O(\text{log}^2N)$. Now for each prime $p$ up to B, compute the remainder of $N$ after dividing by the largest power of $p$ that is smaller than $N$. Use this to populate an array of length of your interval with powers of $p$ which are the factors of the corresponding numbers. This should take (B/log(B)) times $O(\text{log}N)$ time and space.

At this point you have several options. The simplest one is to perform the divisions and list out the cofactors as well as the small factors. Even with B smaller than Felipe's suggestion, you will most likely have printed out the complete factorization of one of the numbers. Use whatever time you have remaining to find it, either by doing quick primality tests on all the candidates or slow primality test on some appropriate subset. An alternative is to continue eliminating small factors, for once $p$ is larger than your $O(\text{log}N)$, you won't need to worry about picking powers, but can switch to doing gcd with 0 or 1 numbers in the interval.

In short, there is a way to make an efficient version which is morally equivalent to trial division, and still have time left over to pick with high chance of success the completely factored number.

EDIT 2011.08.10 I got curious, so I asked a question and did some computations with B=2, with the expectation that I would find very few intervals of the form $[N - \text{log}_2N ,N]$ which did not contain a prime or a power of 2 times a prime, or a power of 2. The data so far are contrary to my expectations: if I haven't messed up the programming, there are more than 200 such $N$ less than $10^5$. Although I still think the small intervals will contain a B-smooth number for B not too large, this recent data puts a measure of doubt in my mind. END EDIT 2011.08.10

Yes, but I am not a professional number theorist, so you should not trust it. I asked a related question, and noted that Knuth and Trabb-Pardo did some relevant calculations. If you look up Hans Riesel's book or the K&T paper, you could come back here and formulate a precise question that might get a good estimate. It is my belief that if $B$ is greater than the log(N)-th prime, and you do Fermat primality tests, the probability is close to 1. Gerhard "Ask Me About System Design" Paseman, 2011.08.04 – Gerhard Paseman Aug 4 '11 at 18:23
If you believe Cramér's conjecture, for all integers in your interval, trial divide up to $(\log N)^2$ and test primality of the cofactor.
I've already learned that via a discussion on Math SE. However, my question demands no unproven assumption, and the bound is $O(\log N)$ instead of $O(\log^2 N)$. On the bright side, I'm not seeking a prime in the interval; any easy-to factor composite number will do. – M.S. Dousti Aug 4 '11 at 11:26