8
$\begingroup$

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 https://math.stackexchange.com/questions/54580.

Spin-off: https://math.stackexchange.com/questions/54719.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – James Cranch
    Commented Aug 4, 2011 at 14:48
  • 1
    $\begingroup$ related: cstheory.stackexchange.com/questions/7491/… $\endgroup$
    – Kaveh
    Commented Aug 4, 2011 at 15:15

2 Answers 2

Reset to default
6
$\begingroup$

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

Gerhard "Ask Me About System Design" Paseman, 2011.08.04

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting. Do you have an estimate on the success probability of this approach? $\endgroup$
    – Sadeq Dousti
    Commented Aug 4, 2011 at 18:13
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 4, 2011 at 18:23
  • $\begingroup$ In fact, there may be results on the density of Carmichael numbers which might let you assert with confidence something like "At least two of n, n+1, and n+2 are completely factored", and then you could do AKS primality on your favorite candidate. Again, you should ask a professional about this; my experience suggests this is a promising path, however. Gerhard "Not A Professional Number Theorist" Paseman, 2011.08.04 $\endgroup$
    – Gerhard Paseman
    Commented Aug 4, 2011 at 18:29
  • $\begingroup$ @Gerhard: Thanks a lot for the pointers. It seems that I need to read more, and then come back... $\endgroup$
    – Sadeq Dousti
    Commented Aug 5, 2011 at 0:35
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sadeq Dousti
    Commented Aug 4, 2011 at 11:26
  • $\begingroup$ How about replacing trial division with Lenstra's elliptic curve factoring and look for slightly smaller prime cofactors? Lenstra's algorithm is not polynomial-time in its usual formulation but if you only need small factors it might be. BTW, I think looking for "prime times small" is your only hope. $\endgroup$
    – Felipe Voloch
    Commented Aug 4, 2011 at 12:02
  • $\begingroup$ The "spin off" link above follows the same idea of small prime factors. More specifically, it defines polylog-smooth integers as integers whose largest factors are poly logarithmic in N. Polylog-smooth integers are not exactly what I'm after, but even this generalization is left unanswered. $\endgroup$
    – Sadeq Dousti
    Commented Aug 4, 2011 at 14:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .