Name
Abstract | ||
|---|---|---|
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 basis reduction algorithms to find short non-zero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/3-540-46416-6_4 | EUROCRYPT |
Field | DocType | Volume |
Merkle–Hellman knapsack cryptosystem,Discrete mathematics,Subset sum problem,Combinatorics,Lattice (order),Algorithm,Time complexity,Mathematics,Lattice reduction,Low density | Conference | 547 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-54620-0 | 44 |
PageRank | References | Authors |
4.47 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthijs J. Coster | 1 | 231 | 38.41 |
| Brian A. LaMacchia | 2 | 804 | 103.59 |
| Andrew M. Odlyzko | 3 | 1286 | 413.71 |