Short Solutions of Ax = b: Lattice Embedding at Scale

Many integer problems reduce to this one: given an integer matrix $A$ with fewer rows than columns and a right-hand side $b$ , find an integer vector $x$ with $Ax = b$ whose entries are small. Balancing a set of weighted items into prescribed totals, finding a small-coefficient combination of measured quantities, and checking whether an integer program with bounded variables is feasible all have this shape. Linear algebra finds some integer solution quickly when one exists; the hard part is finding a short one. This guide builds the lattice that makes the short solution a short vector, sizes it with the tools from embedding basics, and then runs it at 40, 60, 80 and 100 unknowns with g6k-rs.

The problem and the small object

Let $A \in \mathbb{Z}^{k \times n}$ with $k < n$ and $b \in \mathbb{Z}^k$ . We want $x \in \mathbb{Z}^n$ with $Ax = b$ and $\|x\|$ as small as possible. The small object is $x$ itself. The relation is linear and exact over the integers, with a constant term $b$ , so step 2 of the recipe says: build the integer kernel of $A$ , then homogenize to handle the constant.

The set of all integer solutions is a coset $x_p + \ker_{\mathbb{Z}}(A)$ : one particular solution plus any integer vector that $A$ sends to zero. Shortest-vector algorithms work on lattices, not cosets, so the extra coordinate carries the $-b$ and turns the coset into a lattice. This is the same move as the Kannan embedding, applied to an equation instead of a target point.

The embedding

Rows are basis vectors, as in g6k-rs. Write $a_i \in \mathbb{Z}^k$ for the $i$ -th column of $A$ . The basis has $n+1$ rows and $n+k+1$ columns:

B = \begin{pmatrix} I_n & N A^{\top} & 0 \\ 0 & -N b^{\top} & M \end{pmatrix}, \qquad \text{row } i = (e_i \mid N a_i^{\top} \mid 0), \quad \text{last row} = (0 \mid -N b^{\top} \mid M).

A lattice vector is an integer combination $(x, c) \cdot B$ , which equals

(x,\ c) \cdot B = \bigl(x \ \big|\ N (Ax - cb)^{\top} \ \big|\ cM\bigr).

Every entry of the middle block is a multiple of $N$ , so any vector with $Ax \ne cb$ has length at least $N$ . With $N$ larger than the vectors we care about, the short vectors all satisfy $Ax = cb$ exactly, and the ones with $c = \pm 1$ are solutions of the original system. The planted answer is the vector with $c = 1$ :

v^\star = (x \mid 0 \mid M), \qquad t = \|v^\star\| = \sqrt{\|x\|^2 + M^2}.

What the reducer effectively sees

The vectors with a zero middle block form the lattice $L_0 = \{(x, cM) : x \in \mathbb{Z}^n,\ c \in \mathbb{Z},\ Ax = cb\},$ the integer kernel of $A' = [A \mid -b]$ with its last coordinate scaled by $M$ . If $A'$ has rank $k$ , then $\dim L_0 = d = n + 1 - k$ . For $M = 1$ and a row lattice of $A'$ that is saturated (true for random $A$ with high probability), $\det(L_0) = \sqrt{\det\bigl(A' A'^{\top}\bigr)}, \qquad \mathrm{gh}(L_0) \approx \sqrt{\frac{d}{2\pi e}}\, \det(L_0)^{1/d}.$ Each equation removes one dimension and multiplies the determinant by roughly the length of a row of $A$ . If the row lattice is not saturated, the kernel is denser than this formula says, and the target has more competition.

Choosing N and M

M balances the target. In the experiments below the planted $x$ has entries in $\{-1, 0, 1\}$ , so $M = 1$ makes the homogenizing coordinate the same size as the others. A much larger $M$ makes the target long; a smaller one is impossible for integers. If your entries are bounded by $s$ , start with $M \approx s$ . If the entries have a known nonzero centre $\mu$ , subtract $\mu \cdot A\mathbf{1}$ from $b$ first so the unknowns are centred at zero.

N only has to dominate. A vector that breaks an equation pays at least $N$ in length, so choosing $N$ a few times larger than the target length $t$ rules those vectors out. Beyond that, a larger $N$ changes nothing mathematically and only inflates the numbers. We ran the same 60-unknown instance ( $t \approx 6.3$ ) with different $N$ :

$N$	1	4	16	64	256	512	1024	2048	4096
Block size that found $x$	not found by 60	25	35	40	35	25	35	25	15

With $N = 1$ the middle block does not dominate: vectors that violate the equations are just as short as solutions, and the reducer never isolates the answer. From $N = 4$ on, every run succeeded, and the block size needed moved between 15 and 40 with no trend. That spread is ordinary run-to-run variation of BKZ near the threshold, not an effect of $N$ . (Even $N = 4$ , below $t$ , worked here: with entries of $A$ up to 1000, vectors whose middle block is small but nonzero are almost as rare as exact solutions. Do not count on that for small coefficients.) The opposite limit is precision: g6k-rs computes Gram–Schmidt data in double precision. For the 80-unknown instance below with $N = 4096$ , the last row has squared length $3.6 \times 10^{15}$ , within a factor 2.5 of $2^{53} \approx 9.0 \times 10^{15}$ . That run did not find the solution by BKZ-60, but neither did one with $N = 512$ , while runs with 64, 256, 1024 and 2048 did, so variance explains it as well as precision. A large $N$ buys nothing and eats the precision margin, so keep it small. For entries too large for doubles, the crate's arbitrary-precision MpzLatticeBasis reducers avoid the problem.

The complete program

The program generates a random $A$ with entries in $[-R, R]$ , plants a ternary $x$ , sets $b = Ax$ , builds $B$ , and reduces progressively: LLL, then BKZ with block sizes 10, 15, …, 40 using enumeration, then 45 to 60 with the sieve-backed BKZ. After each stage it scans the basis for rows of the form $(x \mid 0 \mid \pm M)$ , checks $Ax = b$ in exact integer arithmetic, and stops once it holds a solution at least as short as the planted one. The optional sixth argument is used in the dimension section.

[dependencies]
g6k-rs = "=0.1.0"

//! Short solutions of A x = b over Z: kernel + homogenization embedding.
//! Rows are basis vectors. Row i < n:  [ e_i | N * A[:, i] | 0 ]
//!                        Row n:       [ 0   | -N * b     | M ]
use g6k_rs::{BKZParams, LatticeBasis, bkz_reduce, bkz_with_sieve, lll};
use std::path::Path;
use std::time::Instant;

/// Tiny deterministic generator (splitmix64) so the instance is reproducible.
struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E3779B97F4A7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
        z ^ (z >> 31)
    }
    fn range(&mut self, lo: i64, hi: i64) -> i64 {
        lo + (self.next() % (hi - lo + 1) as u64) as i64
    }
}

fn embed(a: &[Vec<i64>], b: &[i64], big_n: i64, m: i64) -> Vec<Vec<i64>> {
    let (k, n) = (a.len(), a[0].len());
    let mut rows = Vec::with_capacity(n + 1);
    for i in 0..n {
        let mut r = vec![0i64; n + k + 1];
        r[i] = 1;
        for j in 0..k {
            r[n + j] = big_n * a[j][i];
        }
        rows.push(r);
    }
    let mut last = vec![0i64; n + k + 1];
    for j in 0..k {
        last[n + j] = -big_n * b[j];
    }
    last[n + k] = m;
    rows.push(last);
    rows
}

/// Among rows of the form [x | 0 | ±M] with A x = b, return the shortest x.
fn extract(basis: &LatticeBasis, n: usize, k: usize, m: i64, a: &[Vec<i64>], b: &[i64]) -> Option<Vec<i64>> {
    let mut best: Option<Vec<i64>> = None;
    for row in &basis.basis {
        let v: Vec<i64> = row.iter().map(|&t| t.round() as i64).collect();
        if v[n..n + k].iter().any(|&t| t != 0) || v[n + k].abs() != m {
            continue;
        }
        let s = v[n + k].signum();
        let x: Vec<i64> = v[..n].iter().map(|&t| s * t).collect();
        // Exact check in integers: A x == b.
        let ok = a.iter().zip(b).all(|(r, &bi)| r.iter().zip(&x).map(|(p, q)| p * q).sum::<i64>() == bi);
        let norm = |v: &Vec<i64>| v.iter().map(|t| t * t).sum::<i64>();
        if ok && best.as_ref().map_or(true, |bx| norm(&x) < norm(bx)) {
            best = Some(x);
        }
    }
    best
}

fn main() {
    let args: Vec<String> = std::env::args().collect();
    let n: usize = args.get(1).map_or(40, |s| s.parse().unwrap());
    let k: usize = args.get(2).map_or(7, |s| s.parse().unwrap());
    let r: i64 = args.get(3).map_or(1000, |s| s.parse().unwrap());
    let seed: u64 = args.get(4).map_or(1, |s| s.parse().unwrap());
    let big_n: i64 = args.get(5).map_or(1024, |s| s.parse().unwrap());
    let m: i64 = 1;

    // Random A in [-R, R], planted ternary x, b = A x.
    let mut rng = Rng(seed);
    let a: Vec<Vec<i64>> = (0..k).map(|_| (0..n).map(|_| rng.range(-r, r)).collect()).collect();
    let x0: Vec<i64> = (0..n).map(|_| rng.range(-1, 1)).collect();
    let b: Vec<i64> = a.iter().map(|row| row.iter().zip(&x0).map(|(p, q)| p * q).sum()).collect();

    // Optional: the first g unknowns are known. Move their contribution into b and drop
    // their columns, so the lattice loses g dimensions.
    let g: usize = args.get(6).map_or(0, |s| s.parse().unwrap());
    let b: Vec<i64> = a.iter().zip(&b)
        .map(|(row, &bj)| bj - row[..g].iter().zip(&x0[..g]).map(|(p, q)| p * q).sum::<i64>())
        .collect();
    let a: Vec<Vec<i64>> = a.iter().map(|row| row[g..].to_vec()).collect();
    let x0: Vec<i64> = x0[g..].to_vec();
    let n = n - g;
    let sq = |v: &Vec<i64>| v.iter().map(|t| t * t).sum::<i64>();
    let t = ((x0.iter().map(|v| v * v).sum::<i64>() + m * m) as f64).sqrt();
    println!("n = {n}, k = {k}, R = {r}, N = {big_n}, planted |x|^2 = {}, target norm t = {t:.3}",
        x0.iter().map(|v| v * v).sum::<i64>());

    let mut basis = LatticeBasis::from_integers(&embed(&a, &b, big_n, m));
    let start = Instant::now();
    let _ = lll(&mut basis);
    let report = |label: &str, x: &Option<Vec<i64>>| match x {
        Some(x) => println!("{label}: shortest solution in basis has |x|^2 = {}", sq(x)),
        None => println!("{label}: no row of the form [x | 0 | ±M] yet"),
    };
    let found = extract(&basis, n, k, m, &a, &b);
    println!("LLL: {:.2?}", start.elapsed());
    report("  after LLL", &found);
    if found.as_ref().is_some_and(|x| sq(x) <= sq(&x0)) {
        println!("solved by LLL alone");
        return;
    }

    for beta in [10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] {
        let params = BKZParams { block_size: beta, max_tours: 8, ..Default::default() };
        let t0 = Instant::now();
        if beta <= 40 {
            let _ = bkz_reduce(&mut basis, &params);
        } else {
            // Blocks above params.sieve_threshold (40) are solved by sieving.
            let _ = bkz_with_sieve(&mut basis, &params, Path::new("deep_codes"));
        }
        let found = extract(&basis, n, k, m, &a, &b);
        println!("BKZ-{beta}: {:.2?} (total {:.2?})", t0.elapsed(), start.elapsed());
        report("  after BKZ", &found);
        if let Some(x) = found.filter(|x| sq(x) <= sq(&x0)) {
            println!("x = {:?}", x);
            println!("A x = b checked exactly; equals the planted x: {}", x == x0);
            return;
        }
    }
    println!("not found up to BKZ-60");
}

# BKZ tours above block size 40 use a sieve, which reads spherical-code files.
# They ship inside the published crate; link them next to Cargo.toml:
ln -s ~/.cargo/registry/src/*/g6k-rs-0.1.0/deep_codes deep_codes

# n = 60 unknowns, k = 9 equations (defaults: R = 1000, seed = 1, N = 1024)
cargo run --release -- 60 9

Output on an Apple M3 Max (release build):

$ cargo run --release -- 60 9
n = 60, k = 9, R = 1000, N = 1024, planted |x|^2 = 39, target norm t = 6.325
LLL: 16.18ms
  after LLL: shortest solution in basis has |x|^2 = 166
BKZ-10: 12.93ms (total 29.16ms)
  after BKZ: shortest solution in basis has |x|^2 = 144
BKZ-15: 3.86ms (total 33.04ms)
  after BKZ: shortest solution in basis has |x|^2 = 138
BKZ-20: 10.54ms (total 43.59ms)
  after BKZ: shortest solution in basis has |x|^2 = 104
BKZ-25: 33.46ms (total 77.06ms)
  after BKZ: shortest solution in basis has |x|^2 = 96
BKZ-30: 117.99ms (total 195.06ms)
  after BKZ: shortest solution in basis has |x|^2 = 80
BKZ-35: 1.35s (total 1.54s)
  after BKZ: shortest solution in basis has |x|^2 = 39
x = [0, -1, 1, 0, -1, 1, 0, 1, 0, 1, 0, 1, 1, -1, -1, 0, 1, -1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, -1, -1, 1, 1, 0, 1, 0, -1, 1, -1, 0, 1, 1, 0, 1, 1, -1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1]
A x = b checked exactly; equals the planted x: true

LLL alone finds a solution with $\|x\|^2 = 166$ : a valid answer, but four times longer than the planted one. Each BKZ tour shortens the best solution in the basis until block size 35 exposes the planted vector.

Measured: 40 to 100 unknowns

All instances use $R = 1000$ , seed 1, $N = 1024$ and $M = 1$ . For each size we took two values of $k$ : one comfortably planted and one near the edge. The last two columns before the measurement are the Gaussian heuristic planting ratio and the block size predicted by the usual unique-SVP estimate (the “2016 estimate”: $\sqrt{\beta/d}\, t \le \delta_0^{\,2\beta - d - 1} \det(L_0)^{1/d}$ , evaluated from $\beta = 20$ upward). Both are heuristics.

$n$	$k$	$d = n+1-k$	$\det(L_0)^{1/d}$	$t$	$\mathrm{gh}$	$\mathrm{gh}/t$	estimated $\beta$	measured (total time)
40	7	34	5.52	5.29	7.79	1.47	≤ 20	LLL alone (2.8 ms)
40	6	35	4.18	5.00	5.98	1.20	≤ 20	BKZ-10 (4.0 ms)
60	10	51	5.20	6.00	8.98	1.50	≤ 20	BKZ-10 (27 ms)
60	9	52	4.33	6.32	7.56	1.19	32	BKZ-35 (1.6 s)
80	13	68	5.18	7.14	10.33	1.45	≤ 20	BKZ-30 (0.51 s)
80	12	69	4.46	7.14	8.97	1.26	46	BKZ-40 (35 s)
100	17	84	5.81	7.81	12.88	1.65	40	BKZ-30 (0.77 s)
100	16	85	5.12	7.94	11.42	1.44	51	not found by BKZ-60 (153 s)

Four things stand out. First, one extra equation is worth a lot: at every size, dropping from the larger $k$ to the smaller one lowers the planting ratio and raises the block size needed, at $n = 80$ from a sub-second run to 35 seconds. Second, the estimate is a guide, not a promise: it was within about ten block sizes in every row, in both directions ( $n = 80, k = 13$ needed 30 where it predicts at most 20; $n = 100, k = 17$ fell at 30 where it predicts 40). Third, the same planting ratio means different things at different dimensions: 1.47 was solved by LLL at $d = 34$ , while 1.44 was the hardest case at $d = 85$ . Fourth, the edge is noisy. The last instance failed within BKZ-60 at $N = 1024$ , but a run with $N = 64$ found it at BKZ-40 after 106 seconds.

A practical note on the large block sizes: in these runs the sieve-backed tours at block sizes 45 to 60 finished in seconds and rarely improved the basis. The work that found solutions was done by the enumeration tours up to block size 40. Treat the sieve path in g6k-rs 0.1 as experimental at these sizes and check whether it improves your basis before relying on it.

The dimension trade-off

In this embedding the equations are free: every row of $A$ removes a dimension and raises $\det(L_0)^{1/d}$ , so use all of them. The dimension you can trade is in the unknowns. If some coordinates of $x$ are known (from the application, or from a separate argument), move their contribution to the right-hand side, $b \leftarrow b - A_{\text{known}} x_{\text{known}}$ , and delete their columns. On the hard $n = 80, k = 12$ instance:

known coordinates	$d$	$\det(L_0)^{1/d}$	$t$	$\mathrm{gh}/t$	estimated $\beta$	measured
0	69	4.46	7.14	1.26	46	BKZ-40 (35 s)
5	64	4.99	7.14	1.35	35	BKZ-40 (24 s)
10	59	5.68	7.00	1.51	≤ 20	BKZ-10 (39 ms)
15	54	6.62	6.78	1.73	≤ 20	BKZ-20 (47 ms)

The determinant barely changes when a column goes, but it is now spread over fewer dimensions, so $\det(L_0)^{1/d}$ and the planting ratio rise quickly. Ten known coordinates turned a 35-second run into a 39-millisecond one. When nothing is known, the same idea becomes a trade-off: guess a few coordinates, solve a smaller lattice for each guess, and weigh the number of guesses against the time saved per lattice. How to search the guesses is a separate question; the lattice for each one is built exactly as above.

The mod q variant

If the equations only need to hold modulo $q$ , as in q-ary lattices, add one row per equation that lets it wrap around:

B_q = \begin{pmatrix} I_n & N A^{\top} & 0 \\ 0 & N q I_k & 0 \\ 0 & -N b^{\top} & M \end{pmatrix}.

Now the short vectors are $(x \mid 0 \mid cM)$ with $Ax \equiv cb \pmod q$ . That lattice does not lose dimensions: it sits in $\mathbb{Z}^{n+1}$ with index $q^k$ when $A$ has rank $k$ modulo a prime $q$ , so $d = n + 1$ and $\det = q^k$ . For $n = 40$ , $k = 12$ , $q = 97$ and a planted $x$ with $\|x\|^2 = 16$ : $\det^{1/d} = 97^{12/41} \approx 3.82$ , $\mathrm{gh} \approx 5.91$ , $t = \sqrt{17} \approx 4.12$ , planting ratio 1.43.

//! Short x with A x ≡ b (mod q): the q-ary variant of the embedding.
//! Rows are basis vectors:
//!   row i < n      : [ e_i | N * A[:, i] | 0 ]
//!   row n + j (j<k): [ 0   | N * q * e_j | 0 ]   (lets each equation wrap mod q)
//!   last row       : [ 0   | -N * b      | M ]
use g6k_rs::{BKZParams, LatticeBasis, bkz_reduce, lll};

/// splitmix64, for a reproducible random instance.
fn splitmix(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9E3779B97F4A7C15);
    let mut z = *state;
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
    z ^ (z >> 31)
}

fn main() {
    let (n, k, q, big_n, m) = (40usize, 12usize, 97i64, 1024i64, 1i64);
    let structured = std::env::args().nth(1).as_deref() == Some("structured");
    let mut state = 1u64;
    let a: Vec<Vec<i64>> = (0..k)
        .map(|j| (0..n).map(|i| {
            if structured {
                // A formula instead of random entries: invites unintended short solutions.
                ((7 * i * i + 3 * i * j + 11 * j + 5) as i64) % q
            } else {
                (splitmix(&mut state) % q as u64) as i64
            }
        }).collect())
        .collect();
    let x0: Vec<i64> = (0..n).map(|i| [1, 0, -1, 0, 0][i % 5]).collect(); // planted, |x0|^2 = 16
    let b: Vec<i64> = a.iter().map(|r| r.iter().zip(&x0).map(|(p, v)| p * v).sum::<i64>().rem_euclid(q)).collect();

    let width = n + k + 1;
    let mut rows = Vec::new();
    for i in 0..n {
        let mut r = vec![0; width];
        r[i] = 1;
        for j in 0..k { r[n + j] = big_n * a[j][i]; }
        rows.push(r);
    }
    for j in 0..k {
        let mut r = vec![0; width];
        r[n + j] = big_n * q;
        rows.push(r);
    }
    let mut last = vec![0; width];
    for j in 0..k { last[n + j] = -big_n * b[j]; }
    last[n + k] = m;
    rows.push(last);

    let mut basis = LatticeBasis::from_integers(&rows);
    let _ = lll(&mut basis);
    let _ = bkz_reduce(&mut basis, &BKZParams { block_size: 20, ..Default::default() });

    // Shortest row of the form [x | 0 | ±M], checked against A x ≡ b (mod q).
    let mut best: Option<Vec<i64>> = None;
    for row in &basis.basis {
        let v: Vec<i64> = row.iter().map(|t| t.round() as i64).collect();
        if v[n..n + k].iter().any(|&t| t != 0) || v[n + k].abs() != m {
            continue;
        }
        let x: Vec<i64> = v[..n].iter().map(|t| t * v[n + k].signum()).collect();
        let ok = a.iter().zip(&b).all(|(r, &bj)| {
            (r.iter().zip(&x).map(|(p, v)| p * v).sum::<i64>() - bj).rem_euclid(q) == 0
        });
        let sq = |y: &Vec<i64>| y.iter().map(|t| t * t).sum::<i64>();
        if ok && best.as_ref().map_or(true, |bx| sq(&x) < sq(bx)) {
            best = Some(x);
        }
    }
    let x = best.expect("no solution row found");
    println!("shortest solution: |x|^2 = {}, planted |x0|^2 = {}, equals planted: {}",
        x.iter().map(|t| t * t).sum::<i64>(), x0.iter().map(|t| t * t).sum::<i64>(), x == x0);
}

Output:

$ cargo run --release
shortest solution: |x|^2 = 16, planted |x0|^2 = 16, equals planted: true
$ cargo run --release -- structured
shortest solution: |x|^2 = 4, planted |x0|^2 = 16, equals planted: false

The second run is the lesson. There $A$ comes from a formula instead of random numbers, and its rank modulo 97 is only 2, not 12. The solution lattice then has index $97^2$ instead of $97^{12}$ : it is far denser, its Gaussian heuristic drops to about 1.9, below the target length, and the reducer correctly returns a different, shorter solution. Nothing is wrong with the reduction. The embedding promised a unique short solution that the structure of $A$ did not support.

Workflow for your own system

Write the constraint as $Ax = b$ (or modulo $q$ ) and estimate the size $s$ of the entries you expect. Centre them if they have a known offset.
Remove every unknown you already know, and keep every equation.
Compute $d$ , $\det(L_0)$ , $t \approx \sqrt{\|x\|^2 + M^2}$ , the planting ratio and the estimated block size. Judge feasibility by the block size, not by a fixed ratio: the same ratio that LLL handles at 35 dimensions can need BKZ-40 or more at 85. A ratio at or below 1 means the planted solution is probably not the shortest one.
Build $B$ with $M \approx s$ and the smallest $N$ that clearly dominates, check the rank of $A$ (modulo $q$ in the modular case), then run LLL and progressive BKZ.
After each stage, extract rows with a zero middle block and $\pm M$ in the last coordinate, check $Ax = b$ exactly, and keep the shortest.
For block sizes beyond what enumeration handles in your time budget, switch to sieving, and verify that it improves the basis.

Common mistakes

Unbalanced blocks. If $M$ is much larger than the entries of $x$ , or the unknowns have very different expected sizes, the solution is not the Euclidean-shortest vector even when it is the one you want. Weight each coordinate by the inverse of its expected size.
$N$ that does not dominate. With $N = 1$ our 60-unknown instance was never solved: vectors that break the equations were as short as solutions. A large $N$ , on the other hand, only risks floating-point precision.
Taking the first solution. Rows of the form $(x \mid 0 \mid \pm M)$ appear right after LLL, but they are valid and long. Compare lengths and keep reducing.
Trusting the planting ratio on structured data. A matrix with low rank, repeated rows or a formula behind it has a denser solution lattice than the Gaussian heuristic assumes. Check the rank (modulo $q$ if relevant) before interpreting the numbers.
Forgetting the sign. The reducer is equally happy with $(-x \mid 0 \mid -M)$ . Multiply by the sign of the last coordinate before checking.

7.5 Short solutions of Ax = b: embedding at scale