Well, here is how it works over a field. We take $q=5.$ We will start with $A$ as a 2 by 4,
$$ A \; = \; \left( \begin{array}{cccc}
2 & 3 & 4 & 1 \\
3 & 4 & 0 & 1
\end{array} \right) $$
We begin a sequence of elementary row operations, first multiply the first row times 3 and the second by 2,
$$ \left( \begin{array}{cccc}
1 & 4 & 2 & 3 \\
1 & 3 & 0 & 2
\end{array} \right) $$
Next subtract row 1 from row 2.
$$ \left( \begin{array}{cccc}
1 & 4 & 2 & 3 \\
0 & 4 & 3 & 4
\end{array} \right) $$
then multiply the second row by 4,
$$ \left( \begin{array}{cccc}
1 & 4 & 2 & 3 \\
0 & 1 & 2 & 1
\end{array} \right) $$
Finally add row 2 to row 1,
$$ \left( \begin{array}{cccc}
1 & 0 & 4 & 4 \\
0 & 1 & 2 & 1
\end{array} \right). $$
This is the most favorable case. It allows us to place a little 2 by 2 identity matrix at the bottom when writing the null space we need
$$ \left( \begin{array}{cc}
? & ? \\
? & ? \\
1 & 0 \\
0 & 1
\end{array} \right) $$
which is then forced to become
$$ \left( \begin{array}{cc}
1 & 1 \\
3 & 4 \\
1 & 0 \\
0 & 1
\end{array} \right) $$
This can be readily filled in the way Buchmann, Lindner, Ruckert, Schneider demand at the bottom of page 2,
$$ B \; = \; \left( \begin{array}{cccc}
5 & 0 & 1 & 1 \\
0 & 5 & 3 & 4 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{array} \right). $$
You can check that $AB \equiv 0 \pmod 5$ as the matrix of appropriate size.
What happens instead if the row echelon form comes out with staggered nontrivial 1's? Let us begin again with
$$ A \; = \; \left( \begin{array}{cccc}
1 & 2 & 0 & 3 \\
0 & 0 & 1 & 1
\end{array} \right) $$
It is first necessary to stagger the little 2 by 2 identity matrix in the same way, as in
$$ \left( \begin{array}{cc}
? & ? \\
1 & 0 \\
? & ? \\
0 & 1
\end{array} \right) $$
and forces us to the penultimate
$$ \left( \begin{array}{cc}
3 & 2 \\
1 & 0 \\
0 & 4 \\
0 & 1
\end{array} \right). $$
Note that it is impossible to just place this 4 by 2 as the final two columns of a 4 by 4, BLRS demand nonzero entries on the main diagonal. So what we do is simply stagger the columns with 5's in the same way, giving
$$ B \; = \; \left( \begin{array}{cccc}
5 & 3 & 0 & 2 \\
0 & 1 & 0 & 0 \\
0 & 0 & 5 & 4 \\
0 & 0 & 0 & 1
\end{array} \right). $$
The solutions are of the form $\displaystyle(p, q)= \left(\frac{3t^2nr+n^3}{8},\,\frac{3n^2t+t^3r}{8}\right)$, for any rational parameter $t$. To prove it, we start with $$\left(p+q\sqrt{r}\right)^{1/3}+\left(p-q\sqrt{r}\right)^{1/3}=n\tag{$\left(p,q,n,r\right)\in\mathbb{N}^{4}$}$$
and cube both sides using the identity $(a+b)^3=a^3+3ab(a+b)+b^3$ to, then, get $$\left(\frac{n^3-2p}{3n}\right)^3=p^2-rq^2,$$ which is a nicer form to work with. Keeping $n$ and $r$ fixed, we see that for every $p={1,2,3,\ldots}$ there is a solution $(p,q)$, where $\displaystyle q^2=\frac{1}{r}\left(p^2-\left(\frac{n^3-2p}{3n}\right)^3\right)$. When is this number a perfect square? Wolfram says it equals $$q^2 =\frac{(8p-n^3) (n^3+p)^2}{(3n)^2\cdot 3nr},$$ which reduces the question to when $\displaystyle \frac{8p-n^3}{3nr}$ is a perfect square, and you get solutions of the form $\displaystyle (p,q)=\left(p,\frac{n^3+p}{3n}\sqrt{\frac{8p-n^3}{3nr}}\right).$ Note that when $r=3$, this simplifies further to when $\displaystyle \frac{8p}{n}-n^2$ is a perfect square.
Now, we note that if $\displaystyle (p,q)=\left(p,\frac{n^3+p}{3n}\sqrt{\frac{8p-n^3}{3nr}}\right) \in\mathbb{Q}^2$, $\displaystyle\sqrt{\frac{8p-n^3}{3nr}}$ must be rational as well. Call this rational number $t$, our parameter. Then $8p=3t^2nr+n^3$. Substitute back to get $$(p,q)=\left(\frac{3t^2nr+n^3}{8},\,\frac{3n^2t+t^3r}{8}\right).$$ This generates expressions like $$\left(\frac{2589437}{8}+\frac{56351}{4}\sqrt{11}\right)^{1/3}+\left(\frac{2589437}{8}-\frac{56351}{4}\sqrt{11}\right)^{1/3}=137$$
$$\left(\frac{11155}{4}+\frac{6069}{4}\sqrt{3}\right)^{1/3}+\left(\frac{11155}{4}-\frac{6069}{4}\sqrt{3}\right)^{1/3}=23$$
for whichever $r$ you want, the first using $(r,t,n)=(11,2,137)$ and the second $(r,t,n)=(3,7,23)$.
Best Answer
I'm writing your problem as $y^2 - zx = -3$ In this version, a good starting solution is $(2,1,2).$
Another direction, and likely the only parameterization available, starts by taking integers $$ ad - bc = \pm 1 $$
There are ways to generate the modular group https://en.wikipedia.org/wiki/Modular_group#Finding_elements and determinant $-1$ can be found by negating the lower row, say.
Then create the automorphism matrix
$$ M = \left( \begin{array}{ccc} a^2 & 2ac & c^2 \\ ab & ad+bc & cd \\ b^2 & 2bd & d^2 \\ \end{array} \right) $$
To start with a solution $$ V= \left( \begin{array}{r} x \\ y \\ z \\ \end{array} \right) $$ multiply $MV$ to get a new solution. Note that, with $x,z$ even and $y$ odd, the product $MV$ is the same way.
I was a little worried about finding all solutions, test triples $(14,19,26)$ and variant $(2,19,182).$ Taking $a=-1, b=-13,c=1,d=12.$
for
$$ \left( \begin{array}{ccc} 1 & -2 & 1 \\ 13 & -25 & 12 \\ 169 & -312 & 144 \\ \end{array} \right) \left( \begin{array}{r} 14 \\ 19 \\ 26 \\ \end{array} \right) = \left( \begin{array}{r} 2 \\ 19 \\ 182 \\ \end{array} \right) $$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$