Modular Form Approach to Solving Lattice Problems

摘要: We construct new randomized algorithms to find the exact solutions shortest and closest vector problems (SVP CVP) in l2-norm for integral lattices. Not only minimal norm of non-zero lattice vectors SVP distance CVP, but also how many reach those minimums can be simultaneously computed. Our approach is based on special properties generating function vectors’ l2-norms, lattice-associated theta function. In computational complexity perspective take our solver as an example, family {Λ n } dimension dimΛ = level h l(Λ ) (the positive integer such that dual \(\Lambda_{n}^{*}\) scaled by \(h_{n}^{1/2}\) integral), this algorithm number Λ with success probability 1-e space-complexity polynomial time-complexity (loglogn 2 O(n)log(1/e).