We split the coefficients' matrix into two halves and perform a Meet In The Middle (MITM) attack.
Note:- LLL can be used to solve this (souce: hellman)- One can also setup equations on all monomials with degree <= 2 (source: rkm0959)