Collaborative Research: Short Vectors in Lattices

这个项目的主要焦点是在现代计算机体系结构的基础上重建关于格算法的文献。这意味着超越教科书操作的计算，而是研究具有通信现实限制的并行机器所需的时间，从而获得当前和未来芯片的最终实现效率。主要项目活动包括：基本算术运算的快速恒定时间实现，如整数乘法，欧几里得算法和模反转。2. 大秩格的LLL格基约简算法的可伸缩并行实现。3. 改进了在格中寻找较短向量的算法，包括筛分、枚举和代数数论中的乘法技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.