Regev-Lattices-总结.pdf

简介：
本文档为读者提供了关于格理论在密码学中的应用，特别是RegLattice问题的研究概览和最新进展。它涵盖了该领域的重要概念、算法以及开放性挑战。 本段落档是一份关于格（Lattice）的计算机科学讲义，由特拉维夫大学（Tel Aviv University）的Oded Regev教授在2004年秋季学期课程中整理而成。格是数学领域中的一个重要抽象概念，在物理晶体结构、算法设计、密码学以及计算复杂性理论等多个学科都有广泛应用。 文档详细定义了格的概念，并通过实例说明了如何生成一个格及其基（basis）的含义。具体而言，格是由n个线性独立向量b1, b2, ..., bn生成的一个点集，这些向量都属于Rm空间中。可以表示为L(b1, b2, ..., bn)={x1b1 + x2b2 + ... + xnbn | xi ∈ Z}的形式，其中xi是整数。线性独立意味着不存在一组非零的整数使得这组向量的线性组合等于零向量。 同样地，如果将基向量b1, b2, ..., bn组成的矩阵定义为B，则由该矩阵生成的格可以表示为L(B)={Bx | x ∈ Zn}。这里Zn代表了所有具有n个整数分量的向量构成的空间。格的秩（rank）是指基向量的数量，而维数是Rm空间中的维度m。如果秩等于维数，则称这个格为全秩（full-rank），在大多数情况下我们讨论的是这种类型的格。 课程讲义通过多个实例来具体说明这些概念。例如，由(1,0)T和(0,1)T生成的格是Z2，即所有整数点构成的集合；同样地，基向量也可以选择为(1,1)T和(2,1)T或者更极端的情况如(2005,1)T和(2006,1)T。然而，并非所有的向量组合都能生成Z2：例如，由(1,1)T和(2,0)T组成的集合就不能做到这一点。 除了全秩格的例子外，讲义还提供了一个非全秩的格作为例子——即仅有一个基向量（2,1）T所形成的二维空间中的一个一维子集。同时，文档中也讨论了单维度的全秩格的情况，比如由(1)生成的一维整数点集合Z。 此外，讲义还提及了“张成”的概念，即通过一组基向量可以得到的所有可能线性组合组成的实数空间中的一个子空间{Bx | x ∈ Rn}。这有助于理解在实际问题中如何操作格结构以及它们的性质与应用范围。 这部分内容为读者提供了对计算机科学领域内格的基本理解和实例，为进一步深入探讨格理论及其算法、密码学和复杂性分析的应用奠定了基础。后续课程将更详细地介绍这些方面，并讨论有关计算复杂度的独特属性。