Basis Reduction Algorithms and Subset Sum Problems

Title: en_US Basis Reduction Algorithms and Subset Sum Problems
Creator: en_US LaMacchia, Brian A.
Date: 2004-10-20T19:57:53Z
Date Available: 2004-10-20T19:57:53Z
Date Issued: en_US 1991-06-01
Identifier: en_US AITR-1283
uri: http://hdl.handle.net/1721.1/6813
Abstract: en_US This thesis investigates a new approach to lattice basis reduction suggested by M. Seysen. Seysen's algorithm attempts to globally reduce a lattice basis, whereas the Lenstra, Lenstra, Lovasz (LLL) family of reduction algorithms concentrates on local reductions. We show that Seysen's algorithm is well suited for reducing certain classes of lattice bases, and often requires much less time in practice than the LLL algorithm. We also demonstrate how Seysen's algorithm for basis reduction may be applied to subset sum problems. Seysen's technique, used in combination with the LLL algorithm, and other heuristics, enables us to solve a much larger class of subset sum problems than was previously possible.
Extent: en_US 110 p.; 18362928 bytes; 6467561 bytes
Format: application/postscript; application/pdf
Language: en_US
Relation: en_US AITR-1283
Subject: en_US subset sum problems; en_US knapsack cryptosystems; en_US public keyscryptography; en_US integer lattice; en_US Seysen's algorithm; en_US lattice basissreduction