格基约化算法解低密度子集和问题的复杂度

注意到子集和问题所关联的格L(α,M)的特殊性,本文证明了用文献1～3]所提出的算法求格L(α,M)的约化基或半约化基,其计算量上界至多是用该算法求一般格的约化基或半约化基计算量上界的1/n。特别是,证明了束L(α,M)的半约化基的计算量,当采用快速整数乘法时,可限制在0(n~2(logB_α)~(2+σ))比特运算,只要1≤α_i≤B_α。,1≤i0。本文还给出了用上述算法求解低密度和问题的条件与成功概率。