Metraipolis › archive › dc_beef7db46ae1

Finding a Shortest Vector and More in $2^{n/2+o(n)}$ Time using $q$-ary Coset Difference Tree — arXiv:2609.02764

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.02764
License (as archived): CC0-1.0
Archived: 2026-10-17T05:54:25.631Z
SHA-256 of the archived text: 6dd9b14711b780a116e657443cbb214d0be80ae0ea4b666f946de5c5798e10f2
Stable URL of this page: https://metraipolis.com/documento/dc_beef7db46ae1

How to cite

Finding a Shortest Vector and More in $2^{n/2+o(n)}$ Time using $q$-ary Coset Difference Tree — arXiv:2609.02764 — arXiv (en), https://arxiv.org/abs/2609.02764 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_beef7db46ae1 (Metraipolis archive dc_beef7db46ae1, sha256 6dd9b14711b780a116e657443cbb214d0be80ae0ea4b666f946de5c5798e10f2)

BibTeX

@misc{dcbeef7db46ae1,
  title = {Finding a Shortest Vector and More in $2^n/2+o(n)$ Time using $q$-ary Coset Difference Tree — arXiv:2609.02764},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.02764},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_beef7db46ae1; sha256 6dd9b14711b780a116e657443cbb214d0be80ae0ea4b666f946de5c5798e10f2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02764. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and space $2^{n/2+o(n)}$. Our algorithm can be viewed as a $q$-ary analogue of the midpoint Hessian for an odd prime $q$; more precisely, we use the fact that, for a shortest vector $v$, the gradient (rather than Hessian) of the periodic Gaussian function at $v/q$ is nearly proportional to $v$ (up to sign), even after aggregation over a relatively large random affine coset. We compute the relevant coset gradient along a chain of intermediate lattices using a combinatorial procedure inspired by Wagner's generalized birthday algorithm, yielding the $2^{n/2+o(n)}$ time and space complexity. A variant of the algorithm solves the exact closest vector problem on every input $(y,\mathcal L)$ with a distance guarantee $\operatorname{dist}(y,\mathcal L)\le 1.039\lambda_1(\mathcal L)$ within the same time and space complexity. This guarantee holds for a random target and a random lattice drawn according to the Haar-Siegel measure. Thus, this algorithm solves a closest vector problem on such random instances in time and space $2^{n/2+o(n)}$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.02764 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T05:46:54.685Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).