Posts  / #POST-225316
REDDIT

Found a numerical bug in fplll's GSO + RHF misses structural BKZ/SD-BKZ differences

Z
Apr 22, 2026 · 21:11

Ran a 4,541-seed benchmark of BKZ vs SD-BKZ on LWE-Kannan embeddings (n=50-150, β=20/30/40). Two things worth posting about.

At q=3329 (the ML-KEM modulus), n=100, β=30, 1000-bit MPFR, 38% of reduced bases end with a GSO log-norm sitting at the precision floor (\~-345). fplll's squared-form recurrence in `gso_interface.cpp:147-151` computes `r(i,i) = ||b_i||² - Σ μ_{i,k}² ||b*_k||²` as a single scalar subtraction. No compensation, no reorth, no sign check. Catastrophic cancellation when the sum approaches the norm. A 30-line Kahan-compensated patch takes the failure rate from 38/100 to 0/55, passes all 15 upstream regressions, bit-identical on 13900K and 9950X3D. Same family as fpylll #272 / fplll #237, not a new class.

Second one: the Root Hermite Factor has been the standard comparison metric for these algorithms for \~20 years, and it's blind here. RHF gap < 1e-6 across all 4,541 seeds with no outlier seeds. Li-Nguyen Rankin profile distance gets Cohen's d up to 9.4 at n=100, β=40. Ran a 1000-tour convergence extension at n=90, β=30 and SD-BKZ still hasn't plateaued at 2× the standard extended budget, asymptotic advantage grew \~1.7× over the 70-tour result.

Everything reproducible from a pinned Docker image. Per-seed JSONs, analysis code, LaTeX, the patch, and a SHA-256 seed manifest round-trip bit-identical across three environments.

DOI: [https://doi.org/10.5281/zenodo.19686928](https://doi.org/10.5281/zenodo.19686928)
Repo: [https://github.com/BrendanChambersBourgeois/sdbkz-benchmark](https://github.com/BrendanChambersBourgeois/sdbkz-benchmark)
Paper (30 pp): [https://github.com/BrendanChambersBourgeois/sdbkz-benchmark/raw/main/paper/latex/sdbkz\_paper\_latex.pdf](https://github.com/BrendanChambersBourgeois/sdbkz-benchmark/raw/main/paper/latex/sdbkz_paper_latex.pdf)

First independent project, feedback genuinely welcome. Main things I'm unsure about: whether Kahan is the right fix here or if it should be proper reorthogonalisation on detection, and whether the RHF-decoupling claim holds up methodologically or I'm missing something obvious. Claude Code used on parts of the repo tooling fwiw.