Given a prime number $p$, I am looking to find the smallest positive integer $k$ such that the following equation $$13 + 4 \cdot k \cdot p^2$$ produces a perfect odd square. All variables are integers. For example, for the prime $43$, $k = 3$. For $p=103$ , it turns out that $k = 1391$. A computer program can solve this for small prime numbers. It is easy to prove that $k$ has to be odd too, which improves the search. But for larger primes, say $p>10^4$, the naive approach of incrementing $k$ untill a suitable value is found just takes a long time.
It is important to mention that not all primes have any solution at all. For those which do have a solution, I am interested in an efficient way for finding it.
Is there any other approach to tackle this? Perhaps one that relates to number theory? Or any other field really which may prove useful.