Lattice-based post-quantum cryptography repeatedly multiplies polynomials of degree n = 256. If the naive method of multiplying every pair of coefficients needs about n² multiplications and the method using the number-theoretic transform (NTT) needs about n log₂ n, which is closest to the factor by which the NTT reduces the number of multiplications?

Answer: B. about 1/32

The naive method needs n² = 256² = 65,536 multiplications and the NTT method n log₂ n = 256 × 8 = 2,048, so 65,536 ÷ 2,048 = 32, a reduction to about 1/32. The number-theoretic transform applies the idea of the fast Fourier transform to integers modulo a prime, and after the transform only coefficient-wise multiplication is needed. ML-KEM handles coefficients modulo q = 3329 and is designed to be computed with the NTT, so NTT circuits are a central component of post-quantum cryptography accelerators. In addition, ML-KEM and ML-DSA make heavy use of functions from the SHA-3 family (SHAKE) to generate matrices and randomness, so accelerators for those are also effective.

• A. This answers only log₂ n = log₂ 256 = 8. The ratio is n² ÷ (n log₂ n) = n ÷ log₂ n.
• B. Correct. 256 ÷ 8 = 32.
• C. This is n² ÷ n = n, forgetting to divide by log₂ n.