# Lower bounds for integer factorization

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.

• Perhaps this might be useful: quora.com/… – ajotatxe Jul 11 '17 at 11:17
• I disagree that $t(n)$ must be at least $T(a)$. When factoring $n$, one has information from $n$ which is not available when computing the $a$th prime. If, for instance, $a$ and $b$ are extremely close together then a simple Fermat factorization would be quite fast. – Erick Wong Jul 11 '17 at 12:12
• Thanks for your comment. Ok, so $T(a)$ should be the time to find $p_a$ with additional information that $n=p_a \cdot p_b$ where $n$ and $a<b$ are given in the decimal system. – orgesleka Jul 11 '17 at 12:19
• @stackExchangeUser Ah, so are you primarily interested in the running time for $T(a)$ or for finding the $a$th prime? The former can be done in roughly $O(\exp((\log a)^{1/3}))$ time, but the latter requires something closer to $O(a^{1/2})$. These are not theoretical lower bounds (as far as I know we have no proof that these don't admit polynomial-time solutions), just best-known algorithms. – Erick Wong Jul 11 '17 at 12:27
• @ErickWong Thank you for your answer. What are these algorithms called? – orgesleka Jul 11 '17 at 12:29

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.