No Title

Artificial Intelligence Laboratory

and

Department of Electrical Engineering and Computer Science

Massachusetts Institute of Technology

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, Lovász (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.

Thesis Supervisor:	Silvio Micali
	Associate Professor of Computer Science and Engineering

Company Supervisor:	Andrew M. Odlyzko
	AT&T Bell Laboratories

This report is a revised version of a thesis submitted in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology in May, 1991.

First, my sincerest thanks to Andrew M. Odlyzko, my company supervisor at AT&T Bell Laboratories. This thesis would not have been begun, let alone finished, without Andrew's guidance. Throughout my time at Bell Labs Andrew has been my supervisor, mentor and friend; his initial suggestion that I look at applications of Seysen's algorithm to subset sum problems was the basis for this work. Andrew's support and encouragement were without bound.

I also thank Matthijs J. Coster for his assistance throughout this project. Matthijs suggested numerous variants of Seysen's algorithm and helped design Algorithm SL for solving subset sum problems. His comments on early drafts of this thesis were also quite helpful.

Many people have commented on different aspects of this project while work was in progress. In particular, I'd like to thank Jeff Lagarias, Claus Schnorr and Warren Smith for their assistance.

This work was performed under the auspices of the Center for Mathematical Sciences Research at AT&T Bell Laboratories. I thank Mike Garey, director, and the other members of the Math Center for the research environment they maintain and their constant support during my tenure at Bell Labs.

Many thanks to Professor Silvio Micali, my thesis supervisor at MIT, for overseeing this work. Silvio's enthusiasm for this project never wavered, and his comments when I began writing this thesis were very useful.

Thanks also Professors Harold Abelson and Gerald J. Sussman, and the members of Project MAC (Mathematics and Computation), for their support upon my return from Bell Labs. In particular, thanks to Andy Berlin, Elizabeth Bradley, Mike Eisenberg, Mark Freidman, Arthur Gleckler, Chris Hanson, Stefan Kozlowski, Bill Rozas, Sameer Shalaby, Thanos Siapas, Panayotis Skordos, Franklyn Turbak, Henry Wu, and Feng Zhao. They are a very special group of people.

This project was performed as part of the MIT VI-A Internship Program. The director of the VI-A Program is Kevin O'Toole. Professor Frederic Morgenthaler serves as faculty liaison between the VI-A Office and AT&T Bell Laboratories. At Bell Labs, the VI-A Program is administered by J. Michael Milner and José L. Reyes. My thanks to all of them for making VI-A at Bell Labs so successful.

This paper describes research conducted at AT&T Bell Laboratories, as part of the MIT VI-A Internship Program, and at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the Laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-89-J-3202.