文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

1. Introduction The knapsack or subset sum problem is to nd, given positive integers a;:::; an (the weights) and s, some subset of the ai that sum to s, or equivalently to nd variables e;:::; en, with ei 2 f0; 1g, such that 1 1 X

n

i=1

eiai= s:

(1)

This problem is known to be NP-complete 9] (in its feasibility recognition form), and so is thought to be very hard in general. This has led to the invention of several public-key cryptosystems based on the knapsack problem. Almost all of these have been broken by now, however. (See 2, 3, 5, 15] for surveys of this eld.) Most of the attacks exploited speci c constructions of the relevant cryptosystems. In addition, two algorithms have been proposed, one by Brickell 1] and the other by Lagarias and Odlyzko 11] w

hich show that almost all low-density subset sum problems can be solved in polynomial time. The density of a set of weights a;:::; an is de ned by 1

n d= log max a: i n i 2 1

(2)

The interesting case is d 1, since for d> 1 there will in general be many subsets of weights with the same sum, and so such sets of weights could not be used for transmitting information. The Brickell and Lagarias-Odlyzko algorithms solve almost all subset sum problems with d su ciently small. Both the Brickell and Lagarias-Odlyzko algorithms reduce the subset sum problem to that of nding a short vector in a lattice. The exact complexity of nding short vectors in lattices is not known, and expert opinion appears to be divided as to whether this problem is polynomial or not. At the moment, the best known polynomial time method in this area is the L lattice basis reduction algorithm of Lenstra, Lenstra, and Lovasz 13], which is only guaranteed to nd a non-zero vector in an n-dimensional lattice that is at most an exponential times the length of the shortest non-zero vector in that lattice. If one uses that algorithm, the Lagarias-Odlyzko method can be shown rigorously to solve almost all subset sum problems of density< c=n for large n and for a xed constant c, as is done in 11]. (See 7] for a simpli ed analysis of the algorithm.) Using more recent algorithms of Schnorr 19], one can improve the cuto bound to c0=n for arbitrarily small constants c0> 0, but at the cost of increasing the degree of the polynomial that bounds the running time. 3

上一页第13页

你可能喜欢

热门文档

相关文档

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