g6k-rs Recipes: Lattice Reduction in Rust

g6k-rs is a Rust library for lattice reduction, enumeration and sieving, with optional Metal and CUDA backends. It is a research preview licensed under MIT or Apache-2.0, it has not been audited, and its API may change before 1.0. It is not an official port of the Python/C++ G6K. This page is a cookbook: each recipe states a goal, gives a complete program, and shows what it prints. To design the lattice in the first place, continue with the embedding guides.

A note on the 0.1.0 README

The quickstart in the 0.1.0 README calls LatticeBasis::from_rows and .unwrap() on the result of lll_reduce. Neither compiles against 0.1.0: the constructors are from_integers and new, and lll_reduce returns an LLLResult struct rather than a Result. The recipes below use the published API.

1. Install

Add the crate to Cargo.toml. The default feature set includes mpz, which builds GMP and MPFR from source through rug; the first build takes several minutes. Always run lattice code with --release: debug builds are many times slower.

# Cargo.toml
[dependencies]
g6k-rs = "0.1"

# floating-point API only (no GMP build):
# g6k-rs = { version = "0.1", default-features = false }

Feature	Default	Adds
`mpz`	yes	Exact big-integer bases and reducers (`MpzLatticeBasis`, `mpz_*`)
`metal-gpu`	no	Metal sieve kernels and `bkz_with_gpu_sieve` (macOS)
`metal-fp16`	no	Experimental half-precision GPU database, on top of `metal-gpu`
`cuda-gpu`	no	CUDA sieve, enumeration and Seysen kernels (Linux, needs `nvcc`)

Put each recipe in src/bin/<name>.rs and run it with cargo run --release --bin <name>.

2. Build a basis

Goal: get your matrix into the library. from_integers is the common case and keeps entries integral after every row operation. new takes real rows. For entries beyond $2^{53}$ , use MpzLatticeBasis. The checked constructors (try_from_integers, try_new) reject ragged rows instead of panicking.

use g6k_rs::{LatticeBasis, MpzLatticeBasis};

fn main() {
    // 1. Integer rows (the common case). Each row is one basis vector b_i.
    let b = LatticeBasis::from_integers(&[vec![3, 1], vec![1, 2]]);
    println!("from_integers: {} x {}, integral = {}", b.rows, b.cols, b.is_integral());

    // 2. Real-valued rows. No rounding is applied after row operations.
    let r = LatticeBasis::new(vec![vec![1.0, 0.5], vec![0.25, 2.0]]);
    println!("new:           {} x {}, integral = {}", r.rows, r.cols, r.is_integral());

    // 3. Arbitrary-precision integers, from strings or from i64.
    let big = MpzLatticeBasis::from_strings(&[
        vec!["1", "340282366920938463463374607431768211457"],
        vec!["0", "340282366920938463463374607431768211507"],
    ])
    .expect("not an integer");
    println!("from_strings:  ||b1||^2 = {}", big.norm_sq(1));
    let small = MpzLatticeBasis::from_i64(&[vec![3, 1], vec![1, 2]]);
    println!("from_i64:      det = {}", small.bareiss_determinant().unwrap());

    // Ragged input is rejected by the checked constructor.
    let bad = LatticeBasis::try_from_integers(&[vec![1, 2], vec![3]]);
    println!("ragged rows:   {}", if bad.is_err() { "rejected" } else { "accepted" });
}

Output

from_integers: 2 x 2, integral = true
new:           2 x 2, integral = false
from_strings:  ||b1||^2 = 115792089237316195423570985008687907887978786091576287312721793965953487211049
from_i64:      det = 5
ragged rows:   rejected

3. LLL reduction

Goal: a fast, polynomial-time first reduction. LLLParams::default() is the strong setting $\delta = 0.99$ , $\eta = 0.501$ ; LLLParams::standard() is the original $\delta = 0.75$ . The input below is a skewed basis of a lattice with determinant $-1279$ .

use g6k_rs::{LLLParams, LatticeBasis, lll_reduce};

fn main() {
    // Rows are basis vectors. A skewed basis of a 3-dimensional lattice.
    let rows = vec![
        vec![201, 37, 0],
        vec![1648, 297, 0],
        vec![0, 0, 1],
    ];
    let norms = |b: &LatticeBasis| -> Vec<f64> {
        (0..b.rows).map(|i| b.norm_sq(i).sqrt()).collect()
    };

    let mut b = LatticeBasis::from_integers(&rows);
    println!("input      {:?}  norms {:.2?}", b.basis, norms(&b));

    // Default: strong reduction, delta = 0.99, eta = 0.501.
    let res = lll_reduce(&mut b, &LLLParams::default());
    println!("delta 0.99 {:?}  norms {:.2?}", b.basis, norms(&b));
    println!("converged: {}, swaps: {}, size reductions: {}",
        res.converged, res.num_swaps, res.num_reductions);

    // The original 1982 parameters: delta = 0.75.
    let mut b2 = LatticeBasis::from_integers(&rows);
    let res2 = lll_reduce(&mut b2, &LLLParams::standard());
    println!("delta 0.75 {:?}  norms {:.2?}  swaps: {}", b2.basis, norms(&b2), res2.num_swaps);
}

Output

input      [[201.0, 37.0, 0.0], [1648.0, 297.0, 0.0], [0.0, 0.0, 1.0]]  norms [204.38, 1674.55, 1.00]
delta 0.99 [[0.0, 0.0, 1.0], [1.0, 32.0, 0.0], [40.0, 1.0, 0.0]]  norms [1.00, 32.02, 40.01]
converged: true, swaps: 4, size reductions: 9
delta 0.75 [[0.0, 0.0, 1.0], [1.0, 32.0, 0.0], [40.0, 1.0, 0.0]]  norms [1.00, 32.02, 40.01]  swaps: 4

On this small input both settings give the same basis. In higher dimensions $\delta = 0.99$ produces noticeably shorter vectors for a modest extra cost, which is why it is the default. The converged flag tells you whether the verified LLL conditions hold for the returned basis.

4. Check invariants

Goal: prove the reduction did not change the lattice. A unimodular change of basis keeps $|\det B|$ fixed, and an integer basis must stay integer. GSO::log_det() returns $\sum_i \ln \|\tilde{b}_i\|^2$ , so half of it exponentiated is $|\det B|$ .

use g6k_rs::{
    GSO, LLLParams, LatticeBasis, check_determinant_preserved, check_integral, check_lll_reduced,
    lll_reduce,
};

fn main() {
    let rows = vec![
        vec![4, 1, 3, 2],
        vec![2, 5, 1, 7],
        vec![3, 2, 7, 1],
        vec![9, 4, 2, 5],
    ];
    let mut b = LatticeBasis::from_integers(&rows);
    let before = GSO::new(&b);

    let params = LLLParams::default();
    let res = lll_reduce(&mut b, &params);
    let after = res.gso; // exact GSO of the returned basis

    // log_det() is the sum of ln ||b*_i||^2, so exp(log_det / 2) = |det|.
    println!("|det| before = {:.6}", (before.log_det() / 2.0).exp());
    println!("|det| after  = {:.6}", (after.log_det() / 2.0).exp());
    println!("reduced basis = {:?}", b.basis);

    check_determinant_preserved(&before, &after, 1e-9).expect("lattice changed");
    check_integral(&b).expect("non-integer entries");
    check_lll_reduced(&after, &params).expect("not LLL-reduced");
    println!("all invariant checks passed");
}

Output

|det| before = 339.000000
|det| after  = 339.000000
reduced basis = [[0.0, 3.0, 0.0, 0.0], [-1.0, 1.0, 4.0, -1.0], [-3.0, -1.0, 2.0, 4.0], [4.0, 1.0, 3.0, 2.0]]
all invariant checks passed

Put these three checks in your tests. They catch the most common silent failure: a floating-point basis whose entries grew past exact f64 range, so that the reduced basis describes a slightly different lattice.

5. Progressive BKZ

Goal: shorter vectors than LLL can give. BKZ solves SVP in blocks of block_size consecutive vectors. Run it progressively: small blocks are cheap and leave a better basis for the next, more expensive stage. The example uses a 60-dimensional q-ary lattice with $q = 3329$ and determinant $q^{30}$ .

use std::time::Instant;
use g6k_rs::{BKZParams, GSO, LatticeBasis, lll};

/// Tiny deterministic generator so the example needs no extra crates.
struct XorShift(u64);
impl XorShift {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

/// Basis of the q-ary lattice { x : x = A^T s mod q } in Hermite normal form:
/// rows [ I_k | A' ] followed by [ 0 | q I_(m-k) ]. Its determinant is q^(m-k).
fn qary_basis(m: usize, k: usize, q: i64, seed: u64) -> Vec<Vec<i64>> {
    let mut rng = XorShift(seed);
    let mut rows = vec![vec![0i64; m]; m];
    for i in 0..k {
        rows[i][i] = 1;
        for j in k..m {
            rows[i][j] = (rng.next() % q as u64) as i64;
        }
    }
    for i in k..m {
        rows[i][i] = q;
    }
    rows
}

fn main() {
    let (m, k, q) = (60, 30, 3329);
    let mut basis = LatticeBasis::from_integers(&qary_basis(m, k, q, 1));
    let gh = GSO::new(&basis).gaussian_heuristic();
    println!("dimension {m}, det = {q}^{}, Gaussian heuristic = {gh:.1}", m - k);
    println!("input      ||b0|| = {:.1}", basis.norm_sq(0).sqrt());

    let t = Instant::now();
    let _ = lll(&mut basis);
    println!("LLL        ||b0|| = {:.1}   ({:.2?})", basis.norm_sq(0).sqrt(), t.elapsed());

    // Progressive BKZ: each block size starts from the previous output.
    for block_size in [10, 20, 30] {
        let params = BKZParams { block_size, max_tours: 8, ..Default::default() };
        let t = Instant::now();
        let res = g6k_rs::bkz_reduce(&mut basis, &params);
        println!(
            "BKZ-{block_size:<3}    ||b0|| = {:.1}   ({:.2?}, {} tours, {} SVP calls)",
            basis.norm_sq(0).sqrt(), t.elapsed(), res.tours_completed, res.total_svp_calls
        );
    }
}

Output

dimension 60, det = 3329^30, Gaussian heuristic = 108.1
input      ||b0|| = 10187.1
LLL        ||b0|| = 185.2   (7.23ms)
BKZ-10     ||b0|| = 151.0   (8.40ms, 7 tours, 413 SVP calls)
BKZ-20     ||b0|| = 125.4   (12.95ms, 8 tours, 472 SVP calls)
BKZ-30     ||b0|| = 119.7   (154.81ms, 4 tours, 236 SVP calls)

The Gaussian heuristic, $\mathrm{gh}(L) \approx \sqrt{n/(2\pi e)}\,\det(L)^{1/n}$ , is the length a shortest vector of a random lattice of this determinant would have. It is a yardstick, not a guarantee: here BKZ-30 reaches $1.11 \cdot \mathrm{gh}$ . Time grows steeply with block size, because the default SVP oracle is exact enumeration.

6. Sieve-backed BKZ

Goal: larger block sizes, where a sieve is the better SVP oracle. The sieve needs a directory of spherical-code files for its SimHash filter. The crates.io package ships it as deep_codes/ inside the crate source (~/.cargo/registry/src/*/g6k-rs-0.1.0/deep_codes), and the git repository has the same directory. Pass its path; the example reads it from an environment variable.

G6K_CODES=$(ls -d ~/.cargo/registry/src/*/g6k-rs-0.1.0/deep_codes) \
  cargo run --release --bin sieve_bkz

use std::path::PathBuf;
use std::time::Instant;
use g6k_rs::{
    BKZParams, GSO, LatticeBasis, SvpOracleStrategy, bkz_reduce, bkz_with_parallel_sieve, lll,
};

struct XorShift(u64);
impl XorShift {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

fn main() {
    // Spherical-code files used by the sieve's SimHash filter. They ship in the
    // crate package (…/registry/src/*/g6k-rs-0.1.0/deep_codes) and in the git repo.
    let codes: PathBuf = std::env::var("G6K_CODES").unwrap_or("deep_codes".into()).into();
    assert!(codes.is_dir(), "set G6K_CODES to the deep_codes directory");

    let (m, k, q) = (80usize, 40usize, 3329i64);
    let mut rng = XorShift(11);
    let mut rows = vec![vec![0i64; m]; m];
    for i in 0..m {
        rows[i][i] = if i < k { 1 } else { q };
        if i < k {
            for j in k..m {
                rows[i][j] = (rng.next() % q as u64) as i64;
            }
        }
    }
    let mut lll_basis = LatticeBasis::from_integers(&rows);
    println!("dimension {m}, Gaussian heuristic = {:.1}", GSO::new(&lll_basis).gaussian_heuristic());
    let _ = lll(&mut lll_basis);
    println!("LLL                        ||b0|| = {:.1}", lll_basis.norm_sq(0).sqrt());

    // (a) Progressive BKZ with the exact-enumeration SVP oracle.
    let mut a = lll_basis.clone();
    let t = Instant::now();
    for block_size in [10, 20, 30] {
        let _ = bkz_reduce(&mut a, &BKZParams { block_size, ..Default::default() });
    }
    println!("BKZ-10/20/30 (enumeration) ||b0|| = {:.1}   ({:.2?})", a.norm_sq(0).sqrt(), t.elapsed());

    // (b) BKZ-45 with a BDGL sieve as the SVP oracle, set explicitly.
    let mut b = lll_basis.clone();
    let params = BKZParams {
        block_size: 45,
        max_tours: 2,
        oracle_strategy: Some(SvpOracleStrategy::SieveBDGL { simhash_codes_dir: codes.clone() }),
        ..Default::default()
    };
    let t = Instant::now();
    let _ = bkz_reduce(&mut b, &params);
    println!("BKZ-45 (BDGL sieve)        ||b0|| = {:.1}   ({:.2?})", b.norm_sq(0).sqrt(), t.elapsed());

    // (c) Same block size through the multi-threaded convenience wrapper:
    //     blocks above `sieve_threshold` (default 40) use the parallel sieve.
    let mut c = lll_basis.clone();
    let threads = std::thread::available_parallelism().map(|n| n.get()).unwrap_or(4);
    let t = Instant::now();
    let _ = bkz_with_parallel_sieve(&mut c, &BKZParams { block_size: 45, max_tours: 2, ..Default::default() }, &codes, threads);
    println!("BKZ-45 (parallel sieve)    ||b0|| = {:.1}   ({:.2?}, {threads} threads)", c.norm_sq(0).sqrt(), t.elapsed());
}

Output

dimension 80, Gaussian heuristic = 124.9
LLL                        ||b0|| = 300.4
BKZ-10/20/30 (enumeration) ||b0|| = 164.5   (480.15ms)
BKZ-45 (BDGL sieve)        ||b0|| = 161.3   (1.47s)
BKZ-45 (parallel sieve)    ||b0|| = 188.7   (2.37s, 14 threads)

Two honest observations from this run. Selecting the BDGL sieve explicitly through oracle_strategy gave the shortest vector. The multi-threaded wrapper bkz_with_parallel_sieve was faster per block but ended with a longer first vector on this instance, and in our tests running sieve BKZ-45 on top of the BKZ-30 output did not shorten it further. At these dimensions, compare oracles on your own lattices before committing to one; published G6K experiments put the point where sieving overtakes enumeration around dimension 60–70, above what this page measures.

7. Exact big-integer reduction

Goal: reduce bases whose entries do not fit in 64 bits. The mpz reducers never leave exact integer arithmetic and choose the floating-point precision for their internal Gram–Schmidt data automatically. bareiss_determinant() computes the exact determinant for the check.

use g6k_rs::{MpzLatticeBasis, MpzLllOptions, mpz_bkz, mpz_lll_reduce_with_options};

fn main() {
    // Entries far beyond i64 and f64 precision.
    let mut basis = MpzLatticeBasis::from_strings(&[
        vec!["1", "0", "0", "123456789012345678901234567890123"],
        vec!["0", "1", "0", "987654321098765432109876543210987"],
        vec!["0", "0", "1", "555555555555555555555555555555555"],
        vec!["0", "0", "0", "340282366920938463463374607431768211507"],
    ])
    .unwrap();

    let det_before = basis.bareiss_determinant().unwrap();
    // Exact integer LLL; defaults are delta = 0.99, eta = 0.501, automatic precision.
    let res = mpz_lll_reduce_with_options(&mut basis, MpzLllOptions::default());
    println!("converged: {}, working precision: {} bits", res.converged, res.precision);
    let det_after = basis.bareiss_determinant().unwrap();

    for (i, row) in basis.basis.iter().enumerate() {
        let r: Vec<String> = row.iter().map(|x| x.to_string()).collect();
        println!("b{i} = [{}]  ||b||^2 = {}", r.join(", "), basis.norm_sq(i));
    }
    println!("|det| preserved: {}", det_before.clone().abs() == det_after.clone().abs());

    let _gso = mpz_bkz(&mut basis, 4, 4); // exact BKZ, block size 4, 4 tours
    println!("after mpz_bkz: ||b0||^2 = {}", basis.norm_sq(0));
}

Output

converged: true, working precision: 644 bits
b0 = [1, 10, -18, 3]  ||b||^2 = 434
b1 = [110087045, -10240661, -6258168, -40109112]  ||b||^2 = 13871934146693714
b2 = [-73748143979564, -76118837113782, -74933548365985, -171289118490079]  ||b||^2 = 46187864887810714719190420086
b3 = [65323203007995, -500287251309291, -217481841475377, 340958721176008]  ||b||^2 = 418105655591329194056388950899
|det| preserved: true
after mpz_bkz: ||b0||^2 = 434

The first vector $(1, 10, -18, 3)$ encodes an integer relation among the three large numbers modulo the prime in the last row: $a_1 + 10a_2 - 18a_3 \equiv 3 \pmod p$ . Finding such small relations is the subject of the integer relations guide. In 0.1.0 the older mpz_lll(basis, delta, eta) still works but is deprecated in favour of mpz_lll_reduce_with_options.

8. Closest vector with Babai

Goal: find a lattice point near a target. Babai’s algorithms are fast approximations whose quality depends on the basis: reduce first.

use g6k_rs::{GSO, LatticeBasis, babai_nearest_plane, babai_rounding, lll};

fn main() {
    // A skewed basis (|det| = 455): long, nearly parallel first two rows.
    let rows = vec![vec![97, 101, 0], vec![89, 92, 0], vec![3, 5, 7]];
    let target = vec![10.4, -3.3, 6.8];

    let report = |label: &str, b: &LatticeBasis| {
        let gso = GSO::new(b);
        let np = babai_nearest_plane(b, &gso, &target);
        let rd = babai_rounding(b, &gso, &target);
        println!("{label}");
        let round = |v: &[f64]| v.iter().map(|x| x.round() as i64).collect::<Vec<_>>();
        println!("  nearest plane: {:?}  dist {:.3}", round(&np.closest), np.dist_sq.sqrt());
        println!("  rounding:      {:?}  dist {:.3}", round(&rd.closest), rd.dist_sq.sqrt());
    };

    let mut b = LatticeBasis::from_integers(&rows);
    report("skewed basis", &b);
    let _ = lll(&mut b);
    report("after LLL", &b);
}

Output

skewed basis
  nearest plane: [5, -9, 7]  dist 7.854
  rounding:      [5, -9, 7]  dist 7.854
after LLL
  nearest plane: [13, 0, 7]  dist 4.206
  rounding:      [13, 0, 7]  dist 4.206

With the skewed basis both methods land at distance 7.854; after LLL they find the point at distance 4.206, which a brute-force search over coefficients up to 60 confirms is the true closest point. For stronger guarantees, turn CVP into SVP with the Kannan embedding.

9. Exact and pruned enumeration

Goal: solve SVP exactly in small dimension, or approximately and much faster. A pruning profile gives, for each depth of the enumeration tree (depth 0 is the root), the fraction of the squared radius that may be used. Tight bounds near the root cut most of the tree.

use g6k_rs::{
    BKZParams, EnumConfig, GSO, LatticeBasis, ProjectedBlock, PruningProfile, bkz_reduce,
    enumerate_exact, enumerate_pruned,
};

struct XorShift(u64);
impl XorShift {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

fn main() {
    // A 36-dimensional q-ary lattice. Enumeration cost explodes on a weakly
    // reduced basis, so preprocess with BKZ-10 first.
    let (m, k, q) = (36usize, 18usize, 3329i64);
    let mut rng = XorShift(7);
    let mut rows = vec![vec![0i64; m]; m];
    for i in 0..m {
        rows[i][i] = if i < k { 1 } else { q };
        if i < k {
            for j in k..m {
                rows[i][j] = (rng.next() % q as u64) as i64;
            }
        }
    }
    let mut basis = LatticeBasis::from_integers(&rows);
    let _ = bkz_reduce(&mut basis, &BKZParams { block_size: 10, ..Default::default() });

    let gso = GSO::new(&basis);
    let block = ProjectedBlock::from_gso(&gso, 0, gso.n);
    // Search strictly below the current first vector, so a hit is a genuine improvement.
    let cfg = EnumConfig { max_nodes: 50_000_000, radius_sq: Some(0.999 * block.rr[0]) };
    println!("BKZ-10 ||b0|| = {:.2}, Gaussian heuristic = {:.2}", block.rr[0].sqrt(), gso.gaussian_heuristic());

    let t = std::time::Instant::now();
    let exact = enumerate_exact(&block, &cfg);
    println!(
        "exact         : found {}, norm {:.2}, nodes {:>9}, {:.2?}",
        exact.coeffs.is_some(), exact.norm_sq.sqrt(), exact.telemetry.nodes_visited, t.elapsed()
    );

    // A pruning profile gives, per tree depth d (d = 0 is the root), the fraction
    // of radius^2 allowed. Tighter near the root = fewer nodes, lower success odds.
    let n = gso.n;
    let mut step = vec![1.0; n];
    for d in 0..n / 2 {
        step[d] = 0.5; // half the squared radius over the top half of the tree
    }
    let profiles = [
        ("step 0.5/1.0  ", PruningProfile { radii_sq: step, target_success_prob: 0.5 }),
        ("flat 0.9      ", PruningProfile { radii_sq: vec![0.9; n], target_success_prob: 0.5 }),
        ("linear        ", PruningProfile::linear(n, 0.5)),
    ];
    for (name, profile) in profiles {
        let t = std::time::Instant::now();
        let r = enumerate_pruned(&block, &profile, &cfg);
        println!(
            "{name}: found {}, norm {:.2}, nodes {:>9}, {:.2?}",
            r.coeffs.is_some(), r.norm_sq.sqrt(), r.telemetry.nodes_visited, t.elapsed()
        );
    }
}

Output

BKZ-10 ||b0|| = 101.30, Gaussian heuristic = 83.77
exact         : found true, norm 93.57, nodes   2457205, 29.62ms
step 0.5/1.0  : found true, norm 93.57, nodes     35470, 439.33µs
flat 0.9      : found true, norm 93.57, nodes    962085, 12.04ms
linear        : found false, norm 101.25, nodes         1, 3.17µs

The step profile found the same shortest vector with about 70 times fewer nodes. The built-in linear profile is too tight at the root for this block and missed. When a pruned call misses, norm is just the search radius. The built-in geometric and extreme profiles are tighter still. They are meant for many cheap trials on rerandomized bases (enumerate_rerandomized), not for a single call.

10. The standalone sieve

Goal: use a sieve directly on a whole lattice or a block. Load the Gram–Schmidt data, choose a context window, grow the database, and run BGJ1, BDGL or HK3 (each has a multi-threaded _mt variant).

use g6k_rs::{GSO, LatticeBasis, Siever, SieverParams, lll};

struct XorShift(u64);
impl XorShift {
    fn next(&mut self) -> u64 {
        self.0 ^= self.0 << 13;
        self.0 ^= self.0 >> 7;
        self.0 ^= self.0 << 17;
        self.0
    }
}

fn main() {
    let (m, k, q) = (50usize, 25usize, 3329i64);
    let mut rng = XorShift(3);
    let mut rows = vec![vec![0i64; m]; m];
    for i in 0..m {
        rows[i][i] = if i < k { 1 } else { q };
        if i < k {
            for j in k..m {
                rows[i][j] = (rng.next() % q as u64) as i64;
            }
        }
    }
    let mut basis = LatticeBasis::from_integers(&rows);
    let _ = lll(&mut basis);
    let gso = GSO::new(&basis);
    println!("LLL ||b0|| = {:.1}, Gaussian heuristic = {:.1}", gso.rr[0].sqrt(), gso.gaussian_heuristic());

    let mut s = Siever::new(SieverParams::default(), 42);
    s.load_gso(gso.n, &gso.to_flat_mu_rr());
    s.initialize_local(0, 0, gso.n); // sieve the full context [0, n)
    s.grow_db(4096, 0);
    s.set_threads(8);
    let t = std::time::Instant::now();
    s.bgj1_sieve_mt(0.5);
    println!("db size {}, sieve time {:.2?}", s.db_size(), t.elapsed());

    // best_vector_x() gives integer coefficients on the basis rows in the
    // sieving context. Rebuild the vector itself and measure it exactly.
    let x = s.best_vector_x().expect("empty database");
    let mut v = vec![0.0; basis.cols];
    for (i, &c) in x.iter().enumerate() {
        for j in 0..basis.cols {
            v[j] += c as f64 * basis.basis[i][j];
        }
    }
    let len = v.iter().map(|t| t * t).sum::<f64>().sqrt();
    println!("shortest vector found: length {len:.1} ({:.2} x Gaussian heuristic)", len / gso.gaussian_heuristic());
    // The siever's internal lengths are normalised by the Gaussian heuristic:
    println!("best_vector_len() = {:.3} (squared, in units of gh^2)", s.best_vector_len().unwrap());
}

Output

LLL ||b0|| = 151.8, Gaussian heuristic = 98.7
db size 3963, sieve time 52.54ms
shortest vector found: length 111.0 (1.12 x Gaussian heuristic)
best_vector_len() = 1.264 (squared, in units of gh^2)

One sieve call on the LLL basis took the first vector from $1.54\,\mathrm{gh}$ to $1.12\,\mathrm{gh}$ in about 50 ms. Internally the siever divides lengths by the Gaussian heuristic, which is why best_vector_len() is close to 1. Rebuilding the vector from its coefficients, as above, gives the length in the lattice’s own units.

11. GPU backends

With --features metal-gpu on Apple Silicon, bkz_with_gpu_sieve has the same signature as bkz_with_sieve. With --features cuda-gpu on Linux, set G6K_CUDA_ARCH to your card (for example sm_89) before building. Both backends are experimental and hardware-dependent. We did not run them for this page, so no GPU numbers are shown. Follow docs/TESTING_ON_GPU.md in the repository and validate GPU output against the CPU path with the invariant checks from recipe 4.

12. Choosing a tool

Situation	Start with
Any new basis	`lll` / `lll_reduce`
Entries above about 50 bits	`MpzLatticeBasis` + `mpz_lll_reduce_with_options`
Need shorter vectors, dimension up to about 80	Progressive `bkz_reduce`, block sizes 10 → 20 → 30
Block sizes above about 40	BKZ with a sieve oracle (`SvpOracleStrategy::SieveBDGL`)
Exact SVP, dimension up to about 40	`enumerate_exact` after BKZ preprocessing
A lattice point near a target	`babai_nearest_plane` on a reduced basis, or a Kannan embedding

Measured timings

Apple M3 Max, 14 cores, g6k-rs 0.1.0, --release. Single runs, taken from the outputs above.

Task	Dimension	Time	Result
LLL (q-ary)	60	7.23ms	‖b₀‖ = 185.2
BKZ-10, after previous stage	60	8.40ms	‖b₀‖ = 151.0
BKZ-20, after previous stage	60	12.95ms	‖b₀‖ = 125.4
BKZ-30, after previous stage	60	154.81ms	‖b₀‖ = 119.7
Progressive BKZ-10/20/30 (enumeration)	80	480.15ms	‖b₀‖ = 164.5
BKZ-45, BDGL sieve oracle, from LLL	80	1.47s	‖b₀‖ = 161.3
BKZ-45, parallel sieve wrapper, from LLL	80	2.37s	‖b₀‖ = 188.7
Exact enumeration after BKZ-10	36	29.62ms	norm 93.57, 2,457,205 nodes
Pruned enumeration, step profile	36	439.33µs	norm 93.57, 35,470 nodes
BGJ1 sieve, 8 threads, from LLL	50	52.54ms	‖v‖ = 111.0

Common mistakes

Columns instead of rows. Many textbooks put basis vectors in columns. g6k-rs uses rows; transpose before loading.
Debug builds. Reduction is dominated by tight numeric loops. Always benchmark with --release.
Large entries in f64. Beyond 53 bits the basis is no longer exact. Use the mpz API and check the determinant.
Ignoring the result structs. LLLResult and BKZResult carry converged flags and the final GSO. They are marked #[must_use] for a reason.
One pruned trial as proof. A pruned enumeration that finds nothing does not show that no shorter vector exists.

Check Your Understanding

Q1. You call lll_reduce on a basis. How do you know the result is guaranteed LLL-reduced?
Q2. Your basis entries are 120-bit integers. Which API should you use?
Q3. A pruned enumeration reports found = false. What does that mean?

← Previous4.5Ducas Next →5.1Key PapersThe original sources behind everything on this site.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.

4.6 g6k-rs recipes: lattice reduction in Rust

A note on the 0.1.0 README

1. Install

2. Build a basis

3. LLL reduction

4. Check invariants

5. Progressive BKZ

6. Sieve-backed BKZ

7. Exact big-integer reduction

8. Closest vector with Babai

9. Exact and pruned enumeration

10. The standalone sieve

11. GPU backends

12. Choosing a tool

Measured timings

Common mistakes

Further reading

Check Your Understanding