# 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 & -1 & 0 & 0 \\ S b & 0 & -1 & 0 \\ S c & 0 & 0 & S \\ S p & 0 & 0 & 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 & 0 & 0 & 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

• Can this approach be used with a system of modular equations? – seba Nov 2 at 12:28
• In fact, more interestingly: can you find solutions in which $x$ and $y$ are positive? – seba Nov 3 at 20:56