Basis Reduction Algorithms and Subset Sum Problems

dc.creator	LaMacchia, Brian A.
dc.date	2004-10-20T19:57:53Z
dc.date	2004-10-20T19:57:53Z
dc.date	1991-06-01
dc.date.accessioned	2013-10-09T02:47:02Z
dc.date.available	2013-10-09T02:47:02Z
dc.date.issued	2013-10-09
dc.identifier	AITR-1283
dc.identifier	http://hdl.handle.net/1721.1/6813
dc.identifier.uri	http://koha.mediu.edu.my:8181/xmlui/handle/1721
dc.description	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.
dc.format	110 p.
dc.format	18362928 bytes
dc.format	6467561 bytes
dc.format	application/postscript
dc.format	application/pdf
dc.language	en_US
dc.relation	AITR-1283
dc.subject	subset sum problems
dc.subject	knapsack cryptosystems
dc.subject	public keyscryptography
dc.subject	integer lattice
dc.subject	Seysen's algorithm
dc.subject	lattice basissreduction
dc.title	Basis Reduction Algorithms and Subset Sum Problems

Files in this item

Files	Size	Format	View
There are no files associated with this item.