As stated, I need, for a known integer $a$ to find the integers $b$ that make $a^2+b^2 = k^2$ for some integer $k$.
Alternatively if I can at least find an upper bound for them I can brute force the answer.
EDIT: $k$ is NOT known, it's an arbitrary integer and can be any integer.
Recall (link) the following parametrization of Pythagorean triples: \begin{align} a&=mn& b&=\frac{m^2-n^2}2& k&=\frac{m^2+n^2}2 \end{align} which is valid if $m$ and $n$ are two odd integers such that $m > n$. If $a$ is odd and you can factor it as $a=mn$ and the obtain $b$ and $k$.
If $a$ is even, write $a=2^e\bar a$ with $\bar a$ odd and apply the formula above with $\bar a$ instead of $a$: \begin{align} \bar a&=mn& \bar b&=\frac{m^2-n^2}2& \bar k&=\frac{m^2+n^2}2 \end{align} and take $b=2^e\bar b$ and $k=2^e\bar k$. Then $(a,b,k)$ gives you all Pythagorean triples.