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

何大可

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-12-08

- 格基约化算法解低密度子集和问题的复杂度
- On the Complexity of Solving Low-Density Subset Sum Problem with the Lattice Basis Reduction Algorithm
- 电子学报 1987年第6期页码：82-87
- 作者机构：
  
  西北电讯工程学院
- 作者简介：
- 基金信息：
  
  中国科学院科学基金
- DOI：
  中图分类号：
- 纸质出版：1987
- 稿件说明：
移动端阅览
[1]何大可.格基约化算法解低密度子集和问题的复杂度[J].电子学报,1987(06):82-87.

He Da-ke. On the Complexity of Solving Low-Density Subset Sum Problem with the Lattice Basis Reduction Algorithm[J]. Acta Electronica Sinica, 1987, (6): 82-87.
[1]何大可.格基约化算法解低密度子集和问题的复杂度[J].电子学报,1987(06):82-87. DOI：

He Da-ke. On the Complexity of Solving Low-Density Subset Sum Problem with the Lattice Basis Reduction Algorithm[J]. Acta Electronica Sinica, 1987, (6): 82-87. DOI：

摘要

注意到子集和问题所关联的格L（α

M）的特殊性

本文证明了用文献[1～3]所提出的算法求格L（α

M）的约化基或半约化基

其计算量上界至多是用该算法求一般格的约化基或半约化基计算量上界的1/n。特别是

证明了束L（α

M）的半约化基的计算量

当采用快速整数乘法时

可限制在0(n

（logB

）

2+σ

)比特运算

只要1≤α

≤B

。

1≤i

≥2

0。本文还给出了用上述算法求解低密度和问题的条件与成功概率。

Abstract

Let L（a

M） be a n-dimension integer lattice associated with the subset sumproblem

=M. It is proved that every version of the L3-algorithm in [1

3] working on the L（a

M） can be actually executed at most only in O（*）/n bit operations

where O（*） is the upper bound for processing a general integer lattice with the same scale by using the algorithm[l

3]. Then

some results about the condition and the success rate of using the algorithm mentioned above are given.

关键词

Keywords

references

浏览量

114

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据