1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Perhaps this might be useful: quora.com/… $\endgroup$ – ajotatxe Jul 11 '17 at 11:17
  • 2
    $\begingroup$ 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. $\endgroup$ – Erick Wong Jul 11 '17 at 12:12
  • $\begingroup$ 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. $\endgroup$ – orgesleka Jul 11 '17 at 12:19
  • $\begingroup$ @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. $\endgroup$ – Erick Wong Jul 11 '17 at 12:27
  • $\begingroup$ @ErickWong Thank you for your answer. What are these algorithms called? $\endgroup$ – orgesleka Jul 11 '17 at 12:29
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.