Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

Details Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

2008-01-22

arxiv.org/abs/0801.3331v2

Mathematics

Number Theory

Scientific paper

The Hermite-Korkine-Zolotarev reduction plays a central role in strong lattice reduction algorithms. By building upon a technique introduced by Ajtai, we show the existence of Hermite-Korkine-Zolotarev reduced bases that are arguably least reduced. We prove that for such bases, Kannan's algorithm solving the shortest lattice vector problem requires $d^{\frac{d}{2\e}(1+o(1))}$ bit operations in dimension $d$. This matches the best complexity upper bound known for this algorithm. These bases also provide lower bounds on Schnorr's constants $\alpha_d$ and $\beta_d$ that are essentially equal to the best upper bounds. Finally, we also show the existence of particularly bad bases for Schnorr's hierarchy of reductions.

Affiliated with

Also associated with

No associations

Rating

Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-95203