Schnorr-Euchner 枚举算法

来自SVP综述:原文

研究意义

  • 枚举算法是求解最短向量问题的精确算法。
  • 给定一组格基, 遍历在一定界限之内的所有整系数线性组合, 从而找到最短向量。

主要逻辑

通过将高维空间的问题逐层分解为低维问题,并逐步构造满足条件的向量。

主要内容

Schnorr–Euchner枚举算法:构造一个枚举树

  • 搜索方法:深度优先搜索
  • 深度:$𝑛$
  • 节点:$\forall 1 \le 𝑘 \le𝑛+1$,第$𝑛+1−𝑘$层的节点是所有投影子格$\pi_𝑘(\mathbb{𝐿})$中二范数小于R的向量。
  • 每找到一个新的叶子,更新枚举半径R为叶的范数,更新枚举中心。
  • 枚举范围
  • 算法

对于这个算法过程,总体上枚举是从$\pi_n,\pi_{n-1},\cdots,\pi_1$的顺序来的。但对于算法所示,会先给这个向量的系数给一个初值,然后再去更新枚举中心来根据深度优先搜索去枚举。

评价

  1. 具有精确性,树型搜索结构, Zig-Zag 搜索,应用广泛
  2. 不适合大规模问题,时间复杂度高,很大程度上取决于输入格基的质量
  3. 改进:树型结构适合并行化,剪枝函数

总结

Schnorr-Euchner 枚举算法是一种经典的可以用于求解最短向量问题的枚举方法,广泛应用于密码学和编码理论。为了枚举非零最短向量的每个系数,算法通过对枚举树的深度优先搜索,将高维空间的问题逐层分解为低维空间问题,逐步构造出了满足条件的向量。算法中每次一个新的非零叶子被找到,就会更新枚举半径R为叶子节点的范数。这也说明格基越规约,枚举树中的节点就越少,枚举就越快。尽管算法在低维格中表现良好,但其时间复杂度是超指数的。改进思路包括引入剪枝策略、并行化处理以及利用混合算法等。


Welcome to MinZhang’s space! If you have any questions about the following issues, you can contact me on GitHub or email- zhangmin2022@iie.ac.cn.