Suppose that for some $n\in \mathbb{Z}$ we know that there are $x,y\in \mathbb{Z}$ such that $x^2-dy^2=n$ for some $d\in \mathbb{N}$. Can we say anything about how large $x$ and $y$ are compared to $n$ (say if they are minimal among all such representations)? For positive binary quadratic forms, we can obtain some trivial bounds, but here any bound is non-obvious to me.
I am especially interested in the case where $n$ is prime. For instance, when $d=2$, algebraic number theory tells us that $p$ prime may be written as $x^2-2y^2$ if and only if $p\equiv\pm 1\mod 8 $, but the proof I have seen is ineffective.
$\def\vareps{\varepsilon}$
Note that if $x^2 - d y^2 = n$, then
$$(x - y \sqrt{d})(x + y \sqrt{d}) = n.$$
Equivalently, you are looking of $\alpha \in \mathbf{Z}[\sqrt{n}]$ such that
$$\alpha \overline{\alpha} = n.$$
Let $S$ denote the set of solutions to this equation. Note that if $\alpha \in S$, then $\overline{\alpha} \in S$.
Now suppose there exists an element $\vareps = u + \sqrt{d} v$ with $u^2 - d v^2 = 1$ with $\vareps > 1$. (There always does.) Then its easy to check that if $\alpha \in S$ then $\alpha \vareps \in S$ and also $\alpha \vareps^{-1} \in S$, where $\vareps^{-1} = u - \sqrt{d} v$. This allows you to take a very large solution and make it smaller. The best way to measure the size of an element of $S$ is via the map:
$$S \rightarrow \{(x,y) \in \mathbf{R} \oplus \mathbf{R}, x + y = \log(n)\}, \alpha \rightarrow (\log |\alpha|, \log |\overline{\alpha}|).$$
Hence by multiplying by powers of $\vareps$ one can ensure that
$$\log(n)/2 + \log(\vareps)/2 \ge \log |\alpha| \ge \log(n)/2 \ge \log|\overline{\alpha}| \ge \log(n)/2 - \log(\vareps)/2.$$
This gives the bound
$$|2x| = |\alpha + \overline{\alpha}| \le |\alpha| + |\overline{\alpha}| \le \sqrt{n}(\vareps^{1/2} + \vareps^{-1/2}).$$
In the particular case where $d = 2$, one can take $\vareps = 1 + \sqrt{2}$, and $n = p$, one obtains the bound
$$x < \sqrt{p} \left(\frac{\sqrt{\sqrt{2} + 1} + \sqrt{\sqrt{2} - 1}}{2} \right) = \sqrt{p} \cdot 1.0986841\ldots $$
For example, out of the first 10000 primes, the closest hit is
$$321 - 2 \cdot 94^2 = 85369,$$
where
$$321 = \sqrt{85369} \cdot 1.098638\ldots $$
It turns out that the bound above (with the given constant) is optimal - you can find primes such that $x/\sqrt{p}$ is arbitrarily close to the given number. This is deeper than the inequality above, to prove it, you have to use equidistribution results of characters first proved by Hecke in 1920 using analytic properties of L-functions of characters.
In general, one has the class number formula, which gives a bound rougly of the shape
$$\log |\vareps| < d^{1/2 + \epsilon},$$
(you get a much better bound the bigger the class number is, but one expects $h = 1$ for infinitely many $d$ so you shouldn't expect to do better than this) and so you get a general bound of the form
$$x,y \ll \sqrt{n} \exp \left( d^{1/2 + \epsilon} \right)$$