Using coppersmith for bounded solution of a short linear Diophantine problem

Question

I have a $3$-variable linear Diophantine equation

$$ax+by+cz=r$$ where $a,b,c,r\in\mathbb Z$ are known and can be as large in magnitude as needed and I know the equation has a solution $x,y,z\in\mathbb Z$ which are bounded in magnitude by $T$ where number of bits in $T$ is order of tens of thousands of bits. We can assume magnitude of $a,b,c,r$ is bound below by $T^c$ where $c\geq4$.

Euclid's algorithm gives some solution but not the needed solution. Barvinok's algorithm has complexity $(\log T)^6$ or so which is very prohibitive. Moreover ILP may not be needed as this is a single equality.

Is there a way to solve the problem using Coppersmith's algorithm and if so how?

Answer 1

You could try Coppersmith, but I don't think it will work, as the (heuristic) bounds for this kind of equation don't not seem good enough.

What I think does work is the following:

Let $M$ be a large scaling factor. Define the vectors $$ v_1 = (1,0,0,Ma), \; v_2 = (0,b,0,My), \; v_3 = (0,0,c,Mz) $$ Let $L = <v_1,v_2,v_3>$ be the lattice spanned by these 3 vectors.

Now, define the target vector $t = (0,0,0,Mr)$, and find the closest vector $w \in L$ to $t$.
By choosing $M$ large enough, we get that $w$ is of the form $w = (x,y,z,Mr)$, and hence $ax+by+cz=r$, where $a,b,c$ are basically as small as possible (in absolute value).

In general lattice problems are hard, but this problem is only four-dimensional, so it should be very quick to solve, even if the bit size of the entries is quite large.