Take $a, b \in \mathbb Z / p\mathbb Z$, $p$ being a large prime number.
Suppose there exists a small root $(x, y)$, $x = O(\sqrt p)$ and $y = O(\sqrt p)$ to the equation $y = ax + b \mod p$.
How could one find this root?
I was thinking about using a lattice reduction algorithm, for instance using the fact that
$$1 \cdot \begin{pmatrix}0 \\ -b \\ 1\end{pmatrix} + x \cdot \begin{pmatrix}1 \\ -a \\ 0\end{pmatrix} + \lambda \begin{pmatrix}0 \\ q \\ 0\end{pmatrix} = \begin{pmatrix}x \\ y \\ 1\end{pmatrix}$$ for some $\lambda$, because the resulting vector is quite small, but it does not seem to be enough. And because of the presence of $b$, I could not use only two dimensions.