Collaborative Research: Short Vectors in Lattices

这个项目的主要重点是重建有关格的文献 现代计算机体系结构的基础上的算法。这意味 超越了计算教科书上的操作，而是调查 在并行机上所需的时间与通信的实际限制，以便获得当前和未来芯片上的最终实现效率。 主要项目活动包括以下内容：1.快恒时 基本算术运算的实现，例如整数运算， 乘法、欧几里得算法和模逆。2.一个可扩展 LLL格基约简算法的并行实现 对于大秩格。3.对查找算法的改进 该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

The main focus of this project is to rebuild the literature on lattice algorithms on a foundation of modern computer architecture. This means going beyond counting textbook operations, and instead investigating the time required on a parallel machine with realistic limits on communication, so as to obtain the ultimate implementation efficiency on current and future chips. Major project activities include the following: 1. Fast constant-time implementations of fundamental arithmetic operations such as integer multiplication, Euclid's algorithm, and modular inversion. 2. A scalable parallelized implementation of the LLL lattice-basis-reduction algorithm for large-rank lattices. 3. Improvements to algorithms for finding shorter vectors in lattices, including sieving, enumeration, and multiplicative techniques from algebraic number theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.