NachoPeinador/Galois-Lattice-Pruning

# 分圆格枚举中的 Galois 不变量 []() []() [](https://doi.org/10.5281/zenodo.19920083) [](https://orcid.org/0009-0008-1822-3452) [](https://twitter.com/todos_lumpen) [](https://github.com/NachoPeinador/Galois-Lattice-Pruning/blob/main/Paper/Galois_Invariants_in_Cyclotomic_Lattice_Enumeration.pdf) 论文 **"Galois Invariants in Cyclotomic Lattice Enumeration: Deterministic Collapse of the SVP Search Space via Modular Projection Pruning"** 的官方代码库及补充材料（已提交至 *SEMA Journal*, Springer Nature）。 ## 🎯 太长不看（TL;DR） – 核心要点 ### 🔬 **理论突破** * 🛡️ **Galois 剪枝：** 在分圆环 $\mathbb{Z}[x]/\langle x^n + 1 \rangle$ 上实现了算术超选择定则。拦截并消除代数不一致的分支，完全绕过欧几里得范数约束。 * 📐 **预言机独立性定律：** 解析证明了同时模投影可作为统计独立的过滤器。受限的搜索空间严格由 $|\Omega_{conf}| \approx \frac{|\Omega|}{\prod_{i=1}^k p_i}$ 决定。 * 🌀 **非遍历噪声：** 正式证明了在结构化格中存在对本征态热化假说（ETH）的结构性违反。LWE 误差向量在整个拓扑相空间中不会均匀热化。 * 🧩 **正交整合：** 算术筛与经典的几何边界（例如 Schnorr-Euchner 半径）正交运行，实现了确定性的混合搜索剪枝。 ### ⚡ **计算与物理验证 ($d \le 32$, $k \le 5$)** * 🚀 **MitM 架构：** 高吞吐量的 C++ / OpenMP 引擎，通过高度优化、位压缩的 $\mathcal{O}(N \log N)$ Meet-in-the-Middle 碰撞状态数组克服了 DFS 的“预言机盲区”。 * 📉 **确定性坍缩：** 证明了在 $d=32$ 且带有 $k=5$ 个并行预言机的情况下，节点被精确消除 $>99.99999\%$，将 $1.8 \times 10^{15}$ 个叶子节点压缩至恰好 $157,517$ 条可行路径。 * 🎯 **完美的经验一致性：** C++ 执行结果与理论代数除数方程完美吻合。通过对互质集（例如 $\{17, 19, 23, 29, 31\}$）的严格对照实验验证了不变性。

Figure 1. Deterministic collapse of the LWE search space in dimension d=32. The empirical results (red points) obtained via the C++ MitM engine perfectly align with the theoretical Law of Oracle Independence (dashed line).

### 💡 **核心概念** ## 📌 概述 后量子密码学（PQC）的安全性，特别是像 **ML-KEM** 这样的基于模格的密钥封装机制，依赖于最短向量问题（SVP）假定的指数级难度。当前的安全模型假设注入的 Learning With Errors (LWE) 噪声是遍历的，并且在相空间中均匀分布。 本代码库提供了一个经验框架，证明了这种噪声的**非遍历性**。通过利用分圆环 $\mathbb{Z}[x]/\langle x^n + 1 \rangle$ 中的理想结构，我们应用同时算术约束（Galois 剪枝）来拦截代数不一致的分支。 通过使用 C++ 和 OpenMP 编写的、高度优化的 **Meet-in-the-Middle (MitM)** 架构，我们证明了 SVP 搜索空间根据预言机独立性定律发生确定性坍缩： $$|\Omega_{conf}| \approx \frac{|\Omega|}{\prod_{i=1}^k p_i}$$ ## 🚀 关键实验结果 我们的 MitM 引擎在三进制噪声 $\{-1, 0, 1\}$ 下，评估了维度高达 $d=32$ 时幸存候选向量的总数。仅 5 个模预言机的交集就消除了原始搜索空间的 **>99.99999%**，证明了在结构化格中对本征态热化假说（ETH）的正式违反。 | 维度 | 总叶子数 ($3^d$) | 预言机 | 幸存数 (经验 C++) | 理论期望值 | |---------|------------------------|-------------|---------------------------|-------------------------| | 20 | 3,486,784,401 | 1 | 35,945,565 | 35,946,230 | | 20 | 3,486,784,401 | 3 | 3,452 | 3,455 | | 20 | 3,486,784,401 | 5 | 0 | 0 | | 32 | 1,853,020,188,851,841 | 1 | 19,103,300,900,235 | 19,103,300,915,998 | | 32 | 1,853,020,188,851,841 | 3 | 1,836,316,436 | 1,836,326,147 | | 32 | 1,853,020,188,851,841 | 5 | 157,517 | 157,448 | ## 📂 仓库结构 * `SVP_Galois_Pruning_Framework.ipynb`：主要的交互式 Google Colab notebook，包含数学教学、C++ MitM 引擎编译和执行流水线。 * `/src/`：（可选）包含原始 C++ 源文件（`galois_mitm.cpp`）的目录，用于本地编译。 ## 🛠️ 要求与使用 该代码旨在 **Google Colab** 上无缝运行，无需本地配置。它会使用 `g++` 及 `-fopenmp` 和 `-O3` 标志自动编译 C++ 共享库以实现最高性能，并通过 `ctypes` 将其链接到 Python。 如果您更喜欢在 Linux 环境中本地运行，请确保您具备： * `g++`（支持 OpenMP） * `Python 3.x` * `NumPy` ### 快速开始 1. 在 Google Colab 中打开 `SVP_Galois_Pruning_Framework.ipynb`。 2. 依次运行所有单元格。 3. C++ 引擎将被编译，实验将开始执行，重现上面显示的确切维度坍缩表。 [](https://colab.research.google.com/github/NachoPeinador/Galois-Lattice-Pruning/blob/main/Notebooks/SVP_Galois_Pruning_Framework.ipynb) ## ⚖️ 许可 本代码库采用**双许可证**模式，以保护研究的非商业性质，同时鼓励开放的学术合作： 1. **代码与软件（`Notebooks/`、`/src/` 和脚本）：** 在 [PolyForm 非商业许可证 1.0.0](https://polyformproject.org/licenses/noncommercial/1.0.0) 下发布。 *您可以自由地将代码用于学术、个人或教育目的的使用、修改和分享。严禁任何商业用途、变现或整合到专有的付费软件中。* 2. **手稿与视觉资产（`Papers/` 和 `Images/`）：** 在 [知识共享署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)](https://creativecommons.org/licenses/by-nc-sa/4.0/) 下发布。 *您可以自由地出于非商业目的分享和改编理论文本和图形，前提是您提供适当的署名，并在完全相同的许可证下分发您的贡献。* ## 📝 引用

👇 点击查看引用详情

如果这种 Galois 剪枝机制、Meet-in-the-Middle (MitM) C++ 架构或预言机独立性定律（$|\Omega_{conf}| \approx \frac{|\Omega|}{\prod p_i}$）对您的研究有所帮助，请引用相应的手稿： **BibTeX:** ``` @article{peinador2026galois, author = {Peinador Sala, Jos{\'e} Ignacio}, title = {Galois Invariants in Cyclotomic Lattice Enumeration: Deterministic Collapse of the SVP Search Space via Modular Projection Pruning}, journal = {Zenodo}, year = {2026}, note = {Under Review SEMA Journal}, url = {https://doi.org/10.5281/zenodo.19920083} } ``` **APA:**

## 🔭 哲学背景 多年来，密码学界一直将 Learning With Errors (LWE) 中注入的噪声视为不可穿透、毫无特征的一团迷雾——一种在格相空间上完美随机热化的假设。这一几何公理构建了现代后量子密码学看似不可逾越的指数级高墙。 这项工作源于一种范式转变：不再通过欧几里得几何的传统视角观察分圆格，而是透过 Galois 域严格、无情的架构来审视它。通过认识到模投影作为确定性的超选择定则，“随机噪声”被揭示为高度受约束的。这种噪声并非真正的遍历；它受到代数定律的严格约束。 与以前的工作一样，这个分析框架是在传统学术孤岛之外锻造的。它提醒我们，那些被认为不可破解的加密标准，并不一定非要挥舞着大型超级计算机才能受到致命挑战，而是可以通过将极端的数学好奇心、优雅的计算架构以及质疑基础公理的胆识结合起来实现。

标签：C++, C++实现, LWE, Meet-in-the-Middle, MitM, NoSQL, OpenMP, PQC, Python, Python实现, SEMA, Springer, Springer Nature, SVP, TruffleHog, 代数数论, 伽罗瓦不变量, 分圆域, 后量子密码学, 学术论文, 容错学习, 密码分析, 数据擦除, 无后门, 最短向量问题, 格密码学, 格枚举, 模投影剪枝, 算法实现, 计算数学, 逆向工具, 非遍历噪声, 高维几何