Primes of the form $p=x^2-ny^2$ I want to know which primes $p$ can be written in the form $p=x^2-ny^2$ for given $n \in \mathbb{N}$. If $n$ is squarefree, $n \not\equiv 1 \mod 4$ and $\mathbb{Z}[\sqrt{n}]$ is a principal ideal domain, this has been answered here. Is anything known about the other cases?
 A: Check out the book by Cox: Primes of the form $x^2+ny^2$. In this book, Theorem 9.2 gives a reasonable description of primes of the form $p=x^2+ny^2$. I believe the same result (and proof) works verbatim when $n$ is replaced by $-n$ in this theorem. The only difference is that if a prime can be written as $x^2-ny^2$, then it can be written in this form in infinitely many ways. This also means, by Chebotarev's density theorem, that the relative density of these primes is a positive rational number depending on $n$ (which can be determined effectively). 
I also recommend reading Weinstein's excellent recent survey on related (and more general) questions.
P.S. I just realize the question was asked more than a year ago. Still, my answer might be of use for some.
A: There are many primes that can be represented as $p=x^2-ny^2$. Probably infinitely many.
In the following example we keep the multiplier n constant and we vary $y^2$ while skipping the values of $y^2$ that do not produce a prime.
$$13^2-2*1^2=167$$
$$13^2-2*3^2=151$$
$$13^2-2*7^2=71$$
$$13^2-2*9^2=7$$
We can keep y constant and vary the multiplier n (we skip the values of n that do not produce a prime like 4,6).
$$13^2-2*3^2=151$$
$$13^2-8*3^2=97$$
$$13^2-10*3^2=79$$
$$13^2-12*3^2=61$$
$$13^2-14*3^2=43$$
There is nothing special about the square $13^2$. We can use some other square.
$$19^2-2*1^2=359$$
$$19^2-2*5^2=311$$
$$19^2-2*7^2=263$$
$$19^2-2*9^2=199$$
$$19^2-2*13^2=23$$
Note: I only wanted to provide examples of primes $p=x^2-ny^2$ and to show how easy it is to produce them. I know nothing about the theory behind. I wanted to comment but I don't have enough reps. I posted the method to produce these kind of primes on the mathstackexchange site.
https://math.stackexchange.com/questions/2063770/is-this-algorithm-for-generating-primes-any-good
If this is not the answer expected, please delete it. I don't have a problem with that. 
