Small solutions to modular arithmetic linear congruence Let $p$ be a prime number with $N$ bits, let $a,b,c$ be constants. The problem is to find solutions to the equivalent $a x + b y \equiv c \pmod p$ with both having at most $N/2$ bits.

What algorithmic approaches can solve this problem? Does it have any known hardness reduction?
You can use lattice reduction to solve this problem.

Pick a large constant $S\in\mathbb Z$ and consider the lattice spanned by the rows of the following matrix:
$$
L = \begin{pmatrix}
S a &amp; -1 &amp; 0 &amp; 0 \\
S b &amp; 0 &amp; -1 &amp; 0 \\
S c &amp; 0 &amp; 0 &amp; S \\
S p &amp; 0 &amp; 0 &amp; 0 \\
\end{pmatrix}
$$

Now the crucial thing to notice is that some pair $(x,y)\in\mathbb Z^2$ is a solution to your modular equation if and only if $(0,x,y,S)$ is a vector in this lattice.

Moreover, some vector of the form $\vec v=(Sz,x,y,\pm S)$ must be part of a short basis, since $\begin{pmatrix}S c &amp; 0 &amp; 0 &amp; S\end{pmatrix}$ is the only row of $L$ that is non-zero in the last column. Due to the large scaling factor $S$ in the first column, the vector $\vec v$ will in fact satisfy $z=0$, and therefore you can find a short solution by computing a reduced basis of $L$.

Here's a sage transcript that demonstrates this:



sage: p = next_prime(2**32)
sage: N = 1+floor(log(p,2)) # bit length
sage: S = 10**N
sage: a, b, c = randrange(p), randrange(p), randrange(p)
sage: a, b, c
(2206104035, 3690588304, 373686466)
sage: L = matrix(ZZ, [[S*a,-1,0,0], [S*b,0,-1,0], [S*c,0,0,S], [S*p,0,0,0]])
sage: L
[22061040350000000000                   -1                    0                    0]
[36905883040000000000                    0                   -1                    0]
[ 3736864660000000000                    0                    0          10000000000]
[42949673110000000000                    0                    0                    0]
sage: L.LLL()
[           0        49124        -7835            0]
[           0       -31049       -82479            0]
[-10000000000         2330       -37438            0]
[           0         4276       -42601  10000000000]
sage: (4276*a -42601*b) % p == c
True