Finding the n-th prime number

Question

We want to uniquely map hash values to prime numbers. One way to achieve this is storing the first $l$ prime numbers into an ordered list $L$ with size $|L| =l$. When the hash value $h$ calculated, return $L(h)$. However, when the required list size $|L| \approx 2^{512}$ storing the prime numbers in the list $L$ will be impractical.

Another way is; instead of storing the prime numbers, find them when the hash value occurs. So, the first question is given $n$ find the $n$-th prime.

$$\text{find the } n\text{-th prime}, 1 \leq n \leq |L|$$

If the finding the $n$-th prime is not (possible | practical) then we can relax the condition into finding a unique prime for each index $n, 1 \leq n \leq |L|$ so that we can map hash values uniquely into a prime number.

Answer 1

Mathematica uses a number of sophisticated algorithms to find the $n$th prime extremely quickly, through Prime[n]. For instance, it can find the $10^{10}$th prime ($252097800623$) in $0.55$ seconds. It also has NextPrime[k] which very rapidly finds the least prime above $k$. For instance

NextPrime[9384759348709309384503948548553948753]

found the result ($9384759348709309384503948548553948859$) in less than $0.001$ second on a Mac laptop.

You mentioned specifically the "difficulties" above $2^{512}$. Mathematica finds the next prime above that number ($1340780792994259709957402499820584612747936582059239337772356144372176\ 4030073546976801874298166903427690031858186486050853753882811946569946\ 433649006084171$) in $0.002699$ seconds.

Incidentally, this number is $2^{512} + 75$.