Segment LLL reduction of lattice bases using modular arithmetic

Sanjay Mehrotra; Zhifeng Li

doi:10.3390/a3030224

Segment LLL reduction of lattice bases using modular arithmetic

Sanjay Mehrotra^*, Zhifeng Li

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

The algorithm of Lenstra, Lenstra, and Lov́asz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of O(n) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with O(n) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n ^0:5.

Original language	English (US)
Pages (from-to)	224-243
Number of pages	20
Journal	Algorithms
Volume	3
Issue number	3
DOIs	https://doi.org/10.3390/a3030224
State	Published - Sep 2010

Keywords

Fast matrix multiplication
LLL basis reduction
Lattice
Modular arithmetic
Reduced basis
Segments
Successive minima

ASJC Scopus subject areas

Theoretical Computer Science
Numerical Analysis
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.3390/a3030224

Cite this

@article{51ab3dbc4eb54db2a70acecfac25e544,

title = "Segment LLL reduction of lattice bases using modular arithmetic",

abstract = "The algorithm of Lenstra, Lenstra, and Lo{\'v}asz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of O(n) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with O(n) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n 0:5.",

keywords = "Fast matrix multiplication, LLL basis reduction, Lattice, Modular arithmetic, Reduced basis, Segments, Successive minima",

author = "Sanjay Mehrotra and Zhifeng Li",

year = "2010",

month = sep,

doi = "10.3390/a3030224",

language = "English (US)",

volume = "3",

pages = "224--243",

journal = "Algorithms",

issn = "1999-4893",

publisher = "MDPI AG",

number = "3",

}

TY - JOUR

T1 - Segment LLL reduction of lattice bases using modular arithmetic

AU - Mehrotra, Sanjay

AU - Li, Zhifeng

PY - 2010/9

Y1 - 2010/9

N2 - The algorithm of Lenstra, Lenstra, and Lov́asz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of O(n) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with O(n) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n 0:5.

AB - The algorithm of Lenstra, Lenstra, and Lov́asz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of O(n) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with O(n) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of n 0:5.

KW - Fast matrix multiplication

KW - LLL basis reduction

KW - Lattice

KW - Modular arithmetic

KW - Reduced basis

KW - Segments

KW - Successive minima

UR - http://www.scopus.com/inward/record.url?scp=84859631239&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84859631239&partnerID=8YFLogxK

U2 - 10.3390/a3030224

DO - 10.3390/a3030224

M3 - Article

AN - SCOPUS:84859631239

SN - 1999-4893

VL - 3

SP - 224

EP - 243

JO - Algorithms

JF - Algorithms

IS - 3

ER -

Segment LLL reduction of lattice bases using modular arithmetic

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this