Let $P$ be a sufficiently large prime number. Let $x$ be a positive integer, we can write:
$$ \begin{align*} x^2 = kP + a \end{align*} $$
where $0 \leq a < P$. Suppose furthermore that $\sqrt{P} < x < P^{2/3}$, then this implies that $0 < k < P^{1/3}$.
Assuming that as $x$ runs through its range, $a = x^2 \bmod P$ takes on uniformly distributed values in $[0, P)$ (this isn't rigorous but given the quadratic residues are fairly uniformly distributed mod $P$ this is still a good heuristic), then the probability that there exists at least one $x$ such that $a < P^{1/3}$ is well approximated by
$$ \begin{align*} 1 - \left ( 1 - P^{-2/3} \right )^{P^{2/3}} \to 1 - \frac{1}{e} \approx 0.63 \end{align*} $$
which is independent of $P$. In practice I've found this to be pretty reliable and I can find such $x$ for most choices of $P$.
My question is, given a prime $P$, does there exist an efficient algorithm (say, polynomial in $\log P$) to find at least one $x$, if one exists (which as seen above is likely), such that $0 < k < P^{1/3}$ and $0 < a < P^{1/3}$? Of course we can just try all possible values of either $k$ or $a$, but this becomes prohibitively expensive as $P$ grows.
I have tried to apply Coppersmith's method but it does not seem powerful enough for this problem. Lattices seem a natural fit for problems looking for "small solutions" of this kind, but perhaps the fact that $P$ is prime can be of help (since the above does not use the primality of $P$ in any way). Has this problem been studied?