English
Menu

What is Number-theoretic transform?

A transform that applies the idea of the fast Fourier transform to integers modulo a prime. It replaces polynomial multiplication with a transform, coefficient-wise multiplication and an inverse transform, reducing the roughly n² multiplications needed for degree n to roughly n log n. It needs only exact integer arithmetic with no rounding error. It is at the heart of the computation in lattice-based post-quantum cryptography such as ML-KEM and ML-DSA, and acceleration with dedicated circuits is being pursued.

Japanese name: 数論変換

Number-theoretic transform appears in 1 practice question across 1 topic, including Hardware Security: Advanced Topics and Trends.

Field: Hardware Security: Advanced Topics and Trends

Try it: questions about Number-theoretic transform

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?

  1. Aabout 1/8
  2. Babout 1/32
  3. Cabout 1/256
Show answer and explanation

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.

Number-theoretic transform in the explanations

Questions that mention Number-theoretic transform (1)

  1. 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?

Books on Hardware Security: Advanced Topics and Trends Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Post-quantum cryptography Fast Fourier transform (FFT) Modulo operation ML-KEM Arm CCA (Confidential Compute Architecture) CHERI Confidential computing Control-flow integrity DICE (Device Identifier Composition Engine) FIPS 140-3

Back to the glossary