Algorithms to construct Minkowski reduced and Hermite reduced lattice bases

Bettina Helfrich

Theoretical Computer Science 1985

Time bound

n^n/2+o(n)

Space bound

poly(input size)

Source / version date

1985

Comparison variant

Enumeration · superexponential scale

Cost scale

n^{c n + o(n)}

norm

Euclidean ℓ₂

success

Deterministic exact algorithm

model

Classical; polynomial input-size factors suppressed

Assumptions and source notes

The n^{n/2+o(n)} SVP refinement is explicitly attributed to Helfrich 1985 by Hanrot–Stehlé 2007. That later primary research paper was read; the original Helfrich theorem was not retrieved. This row records the checked historical attribution, rather than claiming an independent reading of the 1985 proof. The scale is n log n and must remain separate from singly exponential SVP.

Source location

Introduction, PDF p. 2; §3.3; reference [13]
Version: CRYPTO 2007 author preprint; checked historical attribution

Primary source ↗

@article{helfrich-1985,
  author = {Bettina Helfrich},
  title = {{Algorithms to construct Minkowski reduced and Hermite reduced lattice bases}},
  journal = {Theoretical Computer Science},
  year = {1985},
  volume = {41},
  number = {2--3},
  pages = {125--139},
  doi = {10.1016/0304-3975(85)90067-2},
  url = {https://doi.org/10.1016/0304-3975(85)90067-2},
  cr_date = {1985-12-31},
  cr_date_precision = {year},
  cr_status = {published},
  cr_venue = {Theoretical Computer Science},
  cr_author_ids = {bettina-helfrich}
}