A hierarchy of polynomial time lattice basis reduction algorithms

  • We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Claus Peter SchnorrGND
Parent Title (English):Theoretical Computer Science
Place of publication:Amsterdam [u.a.]
Document Type:Article
Date of Publication (online):2023/09/18
Year of first Publication:1987
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2023/09/18
Page Number:24
First Page:201
Last Page:224
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoCreative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International