# Revision history [back]

If we understand "smaller" by absolute value, then the problem can be posed as finding a short vector in the lattice generated by column vectors: $$\begin{bmatrix} a_1a_3 C & b_1b_3 C & NC & 0 & 0 \\ a_1a_4 & -b_1b_4 & 0 & N & 0\\ a_2 a_3 & - b_2 b_3 & 0 & 0 & N \end{bmatrix}$$ where the constant $C:=\max\{1,\textrm{round}(\frac{\sqrt{N}}{64})\}$ is needed to make the coordinate of a short vector balanced. It is not guaranteed to produce a solution, but if it exists chances are high.

Here is a sample code:

from sage.modules.free_module_integer import IntegerLattice

def mnTSW(N,a1,a2,a3,a4,b1,b2,b3,b4):
C = max(round(sqrt(N)/64),1)
print("C =",C)
M = matrix(ZZ,[(a1*a3*C,b1*b3*C,N*C,0,0),(a1*a4,-b1*b4,0,N,0),(a2*a3,-b2*b3,0,0,N)])
L = IntegerLattice(M.transpose())
TSW = L.shortest_vector()
mn = M.solve_right(TSW)[:2] % N
print("m,n =",mn)
TSW = list(TSW)
TSW[0] //= C
print("T,S,W =",TSW)

mn(1012301,1001,2005,307,423,11,13,17,19)