Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Improved Generic Algorithms for Hard Knapsacks
verfasst von : Anja Becker, Jean-Sébastien Coron, Antoine Joux
Erschienen in: Advances in Cryptology – EUROCRYPT 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1 in time
${\mathcal{\tilde O}}(2^{0.337n})$
and memory
${\mathcal{\tilde O}}(2^{0.256n})$
, thereby improving a 30-year old algorithm by Shamir and Schroeppel. In this paper we extend the Howgrave-Graham–Joux technique to get an algorithm with running time down to
${\mathcal{\tilde O}}(2^{0.291n})$
. An implementation shows the practicability of the technique. Another challenge is to reduce the memory requirement. We describe a constant memory algorithm based on cycle finding with running time
${\mathcal{\tilde O}}(2^{0.72n})$
; we also show a time-memory tradeoff.