Solving the Shortest Vector Problem in 2^(0.7314n+o(n)) Time via Discrete Gaussian Sampling on Superlattices

Yiming Gao · Yansong Feng · Honggang Hu

ePrint 2026/1587

Time bound

2^{0.7314 n + o(n)}

Space bound

2^{0.5 n + o(n)}

Source / version date

3 Aug 2026

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

GFH26

Assumptions and source notes

Preprint claim. The source gives E₀ = 0.73133754… and states the rounded bound 0.7314. This corrects the transposed 0.713 in the illustrative sequence. Source checked; proof not independently audited.

Primary source ↗

@misc{paper-0cb7a1aa50d2,
  author = {Yiming Gao and Yansong Feng and Honggang Hu},
  title = {{Solving the Shortest Vector Problem in 2^(0.7314n+o(n)) Time via Discrete Gaussian Sampling on Superlattices}},
  year = {2026},
  url = {https://eprint.iacr.org/2026/1587},
  cr_date = {2026-08-03},
  cr_status = {preprint},
  cr_author_ids = {yiming-gao; yansong-feng; honggang-hu},
  howpublished = {Cryptology ePrint Archive, Paper 2026/1587}
}