arXiv Open Access 2018

Faster integer multiplication using short lattice vectors

David Harvey Joris van der Hoeven

Lihat Sumber

Abstrak

We prove that $n$-bit integers may be multiplied in $O(n \log n \, 4^{\log^* n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.

Topik & Kata Kunci

cs.SC cs.DS math.NT

Penulis (2)

David Harvey

Joris van der Hoeven

Format Sitasi

APA MLA BibTeX

Harvey, D., Hoeven, J.v.d. (2018). Faster integer multiplication using short lattice vectors. https://arxiv.org/abs/1802.07932

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓