文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Improved low-density subset sum algorithms
侵权投诉

Improved low-density subset sum algorithms

The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on bas

Table 1: Fraction of random subset sum problems solved by a particular reduction algorithm applied to bases L and L0, respectively 50 50 50 66 66 66 66 66 66 66 66

n

50 60 75 76 84 92 100 104 108 112 116

b

0.05 0.55 1.00{{{{ 0.30 0.55 0.60 1.00

L

1.00 1.00{ 0.25 0.80 0.95 1.

00 1.00 1.00 1.00{

L0

known algorithms for lattice basis reduction, applying them to lattice L0 instead of lattice L also yields dramatic improvements, although the results are not as good as they would be in the presence of a lattice oracle. For example, Table 1 presents the comparison obtained in one particular set of experiments. The lattices used were not exactly L and L0, and the reduction algorithm used a combination of ideas from several sources. More extensive data sets and details of the computations are presented in 12]. For each entry in Table 1, n denotes the number of items, and b the number of bits (chosen at random) for each item. For each (n; b) combination, 20 problems were attempted, where in each case ei= 1 for exactly n=2 of the items. The entries for the L and L0 column indicate what fraction of the 20 problems were solved in each case. It would be of interest to obtain similar comparisons for implementations of other algorithms, such as that of 10].

References 1] E. F. Brickell, Solving low density knapsacks. Advances in Cryptology, Proceedings of Crypto '83, Plenum Press, New York (1984), 25-37. 2] E. F. Brickell, The cryptanalysis of knapsack cryptosystems. Applications of

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email