SVP / Classical · worst case

Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)

Xavier Pujol · Damien Stehlé

ePrint 2009/605

PublishedSource checked

Time bound: 2^{2.465 n + o(n)}
Space bound: 2^{1.233 n + o(n)}

Source / version date: 9 Dec 2009
Comparison variant: Classical · worst case
Cost scale: 2^{c n + o(n)}
Norm: Euclidean ℓ₂
Success guarantee: High probability
Computation model: Classical randomized; polynomial factors suppressed
reference: PS09

Assumptions and source notes

Source states time 2.465 and space 1.233. The ePrint is dated 2009 and marks the work as published elsewhere; its publication venue is unspecified there.

Primary source ↗

BibTeXDownload .bib

@misc{paper-11d2e4157eb4,
  author = {Xavier Pujol and Damien Stehlé},
  title = {{Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)}},
  year = {2009},
  url = {https://eprint.iacr.org/2009/605},
  cr_date = {2009-12-09},
  cr_status = {published},
  cr_venue = {ePrint 2009/605},
  cr_venue_short = {ePrint 2009/605},
  cr_author_ids = {xavier-pujol; damien-stehle},
  howpublished = {Cryptology ePrint Archive, Paper 2009/605},
  note = {The ePrint archive reports published elsewhere but gives no publication venue; the linked author publication list identifies this work as ePrint 2009/605.}
}