格构造与格算法研究

The sphere packing problem is a classical problem and is only answered for dimensions 1,2,3. The lattice sphere packing problem is soloved for dimensions 1,2,3,4,5,6,7,8 and 24. We will work on the construction of lattices which are denser than the presently known densest lattices of dimensions in the range 9 to 48 or the high dimensioanl lattices denser than the presently known densest Mordell-Weil lattices. The SVP and CVP problem of lattices play fundamental roles in coding and cryptography. We will work on the algirithm design for these two problems for lattices with some algebraic or number-theoretic structures.

球堆积（sphere packing）问题是问把无限个等半径的球堆积在欧式空间中使得这些球占比的体积达到最大，这是经典数学问题。三维欧氏空间的球堆积问题的Kepler猜测近年被美国学者解决，但三维以上欧氏空间同类问题还没有清楚回答，如果球心是一个格，其对应的格球堆积问题在维数为1，2，3，4，5，6，7，8时在60余年前已经有确定回答，在24维美国学者2009年证明了Leech格是最稠密的24维唯一格球堆积，这一经典问题的这些最近进展被认为是重大进展。但即使在低维例如48维以下或高维怎样构造稠密的格球堆积仍然是重要的和通信，计算机科学，物理学和化学等领域紧密相关的经典数学问题，我们将主要研究低维和高维欧氏空间中稠密格球堆积的构造。格中最短向量问题（SVP）和离欧式空间中点最近格点问题(CVP)的高效率算法设计一直是编码与密码科学基础领域的基本问题，我们将研究有代数或数论结构的格的这两个问题

格是线性无关向量之间整数关系的描述，在基础数学里长江以来是数的几何，离散几何，代数数论，代数几何，Diophantine 逼近的研究对象，也是信息科学中编码与密码学的重要工具，自1982年LLL算法(Lanstra-Lanstra-Lovasz)提出以来，对RSA公钥密码体制的分析与攻击，数的数域分解算法等都有很好的应用。在离散几何中，格球堆积是一个经典难题，就是找到格使得其决定的球堆积稠密度达到尽可能大，这在编码学中也有重要理论意义。我们本项目主要研究了高稠密度格构造，格算法分析，对NTRU密码分析攻击的应用。在本项目研究期间我们也完成了部分编码问题的研究, 在本项目期间我们也承担了某国防保密单位委托项目一项支持国防研究。