Note that finding "a k-digit prime" is not the same as finding "the kth prime." I don't have any strong feelings either way about whether the former would be po

Note that finding "a k-digit prime" is not the same as finding "the kth prime." I don't have any strong feelings either way about whether the former would be possible in polynomial time or not, but I would be pretty shocked if the latter were.