1.1.3.1 早期探索：Ajtai 的最坏情况到平均情况归约

文档摘要

1.1.3.1 早期探索：Ajtai 的最坏情况到平均情况归约 1.1.3.1 早期探索：Ajtai 的最坏情况到平均情况归约 ——一个被教科书轻描淡写、却被实战者反复踩坑的“格基归约”起点你有没有试过，在凌晨三点调试一个看似完美的格密码原型系统，却在第17次运行时突然崩溃，报错信息只有一行冰冷的？你翻遍文献，发现所有教材都把 Ajtai 1996 年那篇开创性论文《Generating Hard Instances of Lattice Problems》当作“理论奠基”，三句话带过：“构造了一个从最坏情况困难性到平均情况困难性的随机归约”“基于模 q 的整数格”“关键在于均匀采样短向量”。可没人告诉你——那个“均匀采样”，在真实机器上根本做不到；