Basis Reduction Algorithms and Subset Sum Problems

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1991
Accession Number
ADA259492

Entities

People

  • Brian A. Lamacchia

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Advanced Electronics
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Annealing
  • Artificial Intelligence
  • Asymetric Encryption
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Cryptography
  • Cubic Lattices
  • Heuristic Methods
  • Mathematics
  • Military Research
  • Polynomials
  • Quenching
  • Security
  • Weight Reduction

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Naval Engineering and Maritime Security
  • Superconducting Magnet Technology