介绍modular lattice的三种演算法.ppt

介紹modular lattice的三種演算法 田錦燕 95/07/28 大 綱 two-dimensional modular lattice 介紹 [LP94] ?M. Lempel, A. Paz,An algorithm for finding a shortest vector in a two-dimensional modular lattice, Theoretical Computer Science, 1994 介紹 [Rote97]? G. Rote, Finding a Shortest Vector in a Two-Dimensional Lattice Modulo m, Theoretical Computer Science, 1997 介紹[Eisenbrand01] F. Eisenbrand, Short Vectors of Planar Lattices via Continued Fractions, Information Processing Letters, 2001 New Algorithm - “Short vectors of two-dimensional modular lattice via continued fractions” 範例 two-dimensional modular lattice 寫作Lm((a,b)),其中0 a,b m , gcd(a,b)=1 ={(ta mod m, tb mod m )|0≦tm} Example: L7((2,3))={(0,0),(2,3),(4,6),(6,2),(1,5),(3,1),(5,4)} An algorithm for finding a shortest vector in a two-dimensional modular lattice (1) An algorithm for finding a shortest vector in a two-dimensional modular lattice (2) Procedure Min-Cross An algorithm for finding a shortest vector in a two-dimensional modular lattice (3) Finding a Shortest Vector in a Two-Dimensional Lattice Modulo m (a,b),(m,0),(0,m)的整數線性組合(如Fig.1)稱為L。 Lm(a,b)為Fig.1中,[0,m-1]2中的向量集合。 L為一般二維lattice,先求得L的basis,再利用basis reduction algorithm找其最短的兩個不平行的向量x1,x2 則有三種可能情況: 1. x1或-x1落在第一象限 2. x2或-x2落在第一象限 3. x2-x1或-(x2-x1)落在第一象限 依上列順序,找落在第一象限的向量,該向量即為Lm(a,b)中的最短向量。 Short Vectors of Planar Lattices Via Continued Fractions 定義： l∞：||c||∞=max{|c1|,|c2|} l1 ：||c||1=|c1|+|c2| l2 ：||c||2=(c12+c22)1/2 Hermite normal form： 最短向量會是 或 或 為 的漸進分數 New Algorithm 參考[Eisenbrand01]中,利用連分數求解二維lattice之最短向量的方法。 已知：Lp(a,b)={(ta mod p, tb mod p)|1≦t≦p-1} Lp(a,b)={(c,e) | } 假設： gcd(a,b)=1 and gcd(a,p)=1 and gcd(b,p)=1 則求Lp(a,b)之最小vector步驟：1.求w = a-1b mod p2.求 之偶漸近分數3.可能最小l1-norm之vector為 範例(1) 以L13(5,11)為例： 方法一： 範例(2) 範例(3) 以L13(5,11)為例： 方法二： L={(5,11),(13,0),(0,13)} 求得L的一組basis： (1,55),(0,13)依Gauss Reduction Algorithm , basis遞減如下: (1,55)-(0,13)-(1,-3)-(4,1) 所以,x1=(1,-3