Lower bounds for integer factorization

Question

Suppose we know that $n=p_a p_b$ where $a<b$ and $n$ are known integers and $p_a$ is the $a$-th prime. ( For example $n = p_{102} \cdot p_{2034}$). Then the time $t(n)$ to factor $n$ is greater then or equal to $T(a)$ = the time to find the $a$-th prime (Edit by comment from Erick Wong:) given $n = p_a \cdot p_b ,a,b$ in the decimal system. So what is the time to find the $a$-th prime number given $n = p_a p_b,a,b$ in the decimal system? This question is related to the number system http://oeis.org/A054841 where in the given representation of a number one "knows" its prime factors.

Answer 1

One way to compute $p_a$ given $n$,$a$,$b$ is to factor $n$. If $a$ and $b$ are extremely close together (like $b=a+1$) then the fastest method may well be a simple Fermat factorization. If $a$ and $b$ are roughly of the same size, then this would fall under a general-purpose algorithm like Number Field Sieve, which takes $O(\exp((\log n)^{1/3 + \epsilon}))$ time.

However, if $b$ is substantially larger than $a$ (say, on the order of $a^2$, perhaps) then $n$ will also be substantially longer than $a$, and it may be more efficient to use something like Lenstra ECM factorization which is faster for small $a$.

At some point (when $b$ is much larger than $a$, maybe exponentially larger) there would be a crossover where it makes sense to ignore $n$ and just focus on computing the $a$th prime. Computing the $a$th prime function is essentially the same as computing $\pi(x)$, the prime-counting function: given either function, you can use binary search to compute the other, so that the running times are at most a $O(\log a)$ factor apart.

Algorithms for computing the prime-counting function $\pi(x)$ are pretty well-studied. In practice this is done by modern forms of the Meissel-Lehmer algorithm which runs in time $O(x^{2/3 + \epsilon})$, which is faster than computing all primes up to $x$ at least for larger $x$, but notably slower than factoring methods for numbers of similar size. See Deleglise and Rivat's paper for more details.

In theory it is possible to compute $\pi(x)$ using high-precision complex arithmetic in time $O(x^{1/2 + \epsilon})$, but this may not be very practical. You might find some informative discussion of this method in William Galway's thesis.