0
$\begingroup$

I'm sure there is some proof that the nth prime can be found. But if we knew, would encryption that relies on primes be easy to decrypt?

$\endgroup$
  • $\begingroup$ An ill posed question Finding the n-th prime number on Math. $\endgroup$ – kelalaka Nov 7 at 19:47
  • 1
    $\begingroup$ TL;DR, only one cryptosystem in common use is based off primes, and we're phasing away from it anyway. And even then, it's based on the difficulty of factoring primes which is not necessarily made easier by being able to find the $n$th prime. $\endgroup$ – Stephen Touset Nov 7 at 20:54
4
$\begingroup$

No. The only plausibly relevant major cryptosystems involving that are RSA-based cryptosystems. A typical RSA prime is chosen uniformly at random from 1024-bit primes, of which there are $\pi(2^{1024}) - \pi(2^{1023}) \approx 2^{1014} - 2^{1013} = 2^{1013}$ possibilities, by the prime-counting approximation $\pi(x) \approx x/\!\log x$. Even if you could efficiently find the 1762496654486650458301017412708452577168455321425338564295164204627851827809673950656701400197184589192372578810839228796442397889449007625305174377608286256232618793314981228756675796669238641660676263338471020306341778397911556529236704830386308649499298417719554769934355960770722959180457300530690137th one, for example, that wouldn't help you to guess which prime I picked. You don't even have a hope of guessing which of the $2^{256}$ ChaCha keys I'm using, and there are a lot fewer of those.

$\endgroup$
1
$\begingroup$

This is for completeness and a complement to the nice answer above.

The $n^{th}$ prime number $p_n$ is not known for large $n$. The best unconditional bounds (i.e., without assuming unproved hypotheses such as the Riemann Hypothesis) are are due to Dusart $$ n\left(\ln n+ \ln\ln n-1+ \frac{\ln \ln n -2.1}{\ln n}\right)\leq p_n \leq n\left(\ln n+ \ln\ln n-1+ \frac{\ln \ln n -2}{\ln n}\right), $$ for $n\geq 688~383.$ This gives you an interval of size roughly $$\frac{n}{10 \ln n}\approx \frac{X}{10 \ln X \ln(X/\ln X)},$$ say around $X=2^{1024}.$

Magma tells me this value of $X$ yields an interval of length

36016401202093992734848699077520151544037300347215601448904318847226665527162111326023510565646939754194973835732156904989863338439213156939387133301740931734002194925153143466001030912699711055456251922934167058148794848690488514642661673725822399003877461223241027943589779640700089648544847778283520

$\endgroup$
  • $\begingroup$ What is specific about the 688383 and 1024-bit RSA? the \approx part is not clear for me. Also, Bounds for n-th prime $\endgroup$ – kelalaka Nov 7 at 22:04
  • 1
    $\begingroup$ The stronger bounds apply for this $n$ or larger due to techniques used. These are the strongest known. If $p_n=X$ then $n$ is approximately $X/\log X$. $\endgroup$ – kodlu Nov 7 at 23:13

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.