An Improved Multi-set Algorithm for the Dense Subset Sum Problem
Given sets L 1, ..., L k of elements from Open image in new window , the k-set birthday problem is to find an element from each list such that their sum is 0 modulo m. We give a new analysis of the algorithm in [16], proving that it returns a solution wit
- PDF / 456,133 Bytes
- 14 Pages / 430 x 660 pts Page_size
- 36 Downloads / 176 Views
Abstract. Given sets L1 , . . . , Lk of elements from Z/mZ, the k-set birthday problem is to find an element from each list such that their sum is 0 modulo m. We give a new analysis of the algorithm in [16], proving that it returns a solution with high probability. By the work of Lyubashevsky [10], we get as an immediate corollary an improved algorithm for the random modular subset sum problem. Assuming the modulus m = 2n for < 1, this problem is now solvable using time and space n
O(2 (1−) log n ).
Let a1 , a2 , . . . , an , t ∈ Z/mZ be given. The modular subset sum problem is to find a subset of the ai that sum to t in Z/mZ, i.e. to find xi ∈ {0, 1} such that n
ai xi = t
mod m .
(1)
i=1
The corresponding decision problem is to determine whether or not there exists x = (x1 , x2 , . . . , xn ) that satisfies (1). A subset sum problem is called random if n, m, and t are all fixed parameters but the ai are drawn uniformly at random from Z/mZ. In addition to being interesting in their own right, random subset sum problems accurately model problems that arise naturally in number theory and combinatorics. We will use the shorthand MSS for modular subset sum and RMSS for random modular subset sum. A useful way of classifying subset sum problems is by density. Definition 1. The density of a MSS instance is logn m . Problems with density 2 less than one are called sparse, while those with density greater than one are called dense. Now let sets L1 , . . . , Lk of elements of Z/mZ be given. The k-set birthday problem is to find bi ∈ Li such that b1 + · · · + bk = 0 mod m. We will assume that the elements of the Li are uniformly generated and independent. A.J. van der Poorten and A. Stein (Eds.): ANTS-VIII 2008, LNCS 5011, pp. 416–429, 2008. c Springer-Verlag Berlin Heidelberg 2008
An Improved Multi-set Algorithm for the Dense Subset Sum Problem
417
In this paper all logarithms will have base 2. Since the main algorithm has exponential complexity, we will often use “Soft-Oh” notation (see [5] for a definition) to highlight the main term and will assume “grade-school” arithmetic for simplicity. This work was part of the author’s dissertation research. Contact the author for further details or for proofs omitted from this paper. Thanks to Eric Bach, Matt Darnall, Tom Kurtz, and Dieter van Melkebeek for thoughtful discussions that proved essential, to NSF award CCF-8635355 and the William F. Vilas Trust Estate for monetary support, and to the referees for helpful comments.
1
Previous Work and Results
The subset sum problem is of great practical and theoretical interest. Its decision version was proven NP-complete by R. Karp in his seminal 1972 paper on reductions among combinatorial problems [8]. It has seen application in the creation of public key cryptosystems [3], and is a vital tool in discovering Carmichael numbers [6]. Trivial algorithms for MSS include brute force enumeration at O(2n ) time and constant space, basic time-space tradeoff at O(2n/2 ) time and space, and dynamic programming at O(n · m) time an
Data Loading...
