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)