Family 109Theoretical computer scienceNo LeanDigested

Integer multiplication below $n\log n$

Multiplies two n-bit integers exactly at every input length in deterministic worst-case time

O(n(\log n)^{1-\kappa})

, with

\kappa=2^{-182}

, on one fixed finite-alphabet Turing machine with finitely many one-dimensional tapes. This disproves the Schönhage–Strassen

n\log n

optimality conjecture in the ordinary multitape bit model.

Manuscripts in this family · 1

Integer multiplication below n log n

Sep 23, 2026·paper.pdfDigested

We give a deterministic algorithm that multiplies two n-bit integers in

O(n(\lg n)^{1-\kappa})

worst-case time, with

\kappa=2^{-182}

, on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the

n\log n

optimality conjecture of Schönhage and Strassen in this model.

Full abstract

Read the map PDF on GitHub LaTeX source

Integer multiplication below nlog⁡nn\log nnlogn

Manuscripts in this family · 1

Integer multiplication below n log n

Integer multiplication below $n\log n$