nt.number theory - When is $Pn^2-2an+frac{a^2-k}{P}$ , with $P$ Prime, $k=a^2 mod P$, a square?

It is easy to show that the following problems are equivalent.

a. When is $Pn^2-2an+frac{a^2-k}{P}$ , with $P$ Prime, $k=a^2 mod P$, and $n$ any integer, a square?

and

b. When is $X^2-PY^2=k$ solvable in integers?

So, any suggestions on problem a ? How fast would an algorithm used to compute this run ?