Division algorithms for the fixed weight subset sum problem

Details Division algorithms for the fixed weight subset sum problem Division algorithms for the fixed weight subset sum problem

2012-01-13

arxiv.org/abs/1201.2739v1

Mathematics

Combinatorics

Scientific paper

Given positive integers $a_1,..., a_n, t$, the fixed weight subset sum problem is to find a subset of the $a_i$ that sum to $t$, where the subset has a prescribed number of elements. It is this problem that underlies the security of modern knapsack cryptosystems, and solving the problem results directly in a message attack. We present new exponential algorithms that do not rely on lattices, and hence will be applicable when lattice basis reduction algorithms fail. These algorithms rely on a generalization of the notion of splitting system given by Stinson. In particular, if the problem has length $n$ and weight $\ell$ then for constant $k$ a power of two less than $n$ we apply a $k$-set birthday algorithm to the splitting system of the problem. This randomized algorithm has time and space complexity that satisfies $T \cdot S^{\log{k}} = O({n \choose \ell})$ (where the constant depends uniformly on $k$). In addition to using space efficiently, the algorithm is highly parallelizable.

Affiliated with

Also associated with

No associations

Rating

Division algorithms for the fixed weight subset sum problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Division algorithms for the fixed weight subset sum problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Division algorithms for the fixed weight subset sum problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-470944