Skip to section
Foundationsfor rotation-free search
Section 36 of 5269% of course
Contents
Chapter 6 Section 6.5 78 min

Part IV · Approximate encrypted arithmetic

A faster representation for the same product

Build the transform motivation from the pair-count bottleneck.

The multiplication table grows quadratically

Two length-N polynomials have N² coefficient pairs. At N=4096, the schoolbook table contains 16,777,216 pairs for just one limb/component product. The output-bucket rule we learned in Chapter 2 is crystal clear but way too costly to execute literally at scale.

Evaluation reveals the massive shortcut

For ordinary polynomials, evaluating a product at a number r obeys (A·B)(r)=A(r)B(r). Multiplication is incredibly difficult in coefficient form because every pair contributes to an output bucket. But at a chosen evaluation point, it is just one simple scalar multiplication. A transform uses a carefully chosen collection of finite-field evaluation-like coordinates that is just rich enough to recover the full coefficient polynomial afterward.

Worked example

The idea with one ordinary point

Let A(x)=2+3x and B(x)=4+x. At x=5, A(5)=17 and B(5)=9, so their product evaluates to 153. Expanding first gives C(x)=8+14x+3x², and C(5)=8+70+75=153. One point cannot recover all of C, but it beautifully demonstrates why evaluation turns a dense polynomial product into a simple pointwise product.

Change your representation, preserve the product

The number theoretic transform is a finite-field relative of the famous Fourier transform. “Finite field” just means its arithmetic uses residues instead of approximate complex numbers. It maps a polynomial into N transform values where multiplication becomes N totally independent pointwise multiplications, then an inverse transform recovers your coefficients.

coefficientsA, B
forward NTT
evaluation formÂ, B̂
N pointwise products
product formĈ[i]=Â[i]B̂[i]
inverse NTT
coefficientsC

Fast transforms use incredibly efficient O(N log N) butterfly operations rather than O(N²) pair enumeration. Corpus polynomials can be transformed once during ingest and saved. A query is transformed exactly once per request. The score engine then just consumes matching transformed positions.

for N=4096: N²=16,777,216 pair products; N log₂N=49,152 butterfly positions

Worked example

What the NTT definitely does not do

It absolutely does not reverse corpus coordinates, choose score taps, encrypt data, or reduce coordinate lanes into a dot product. The reversed packing dictates exactly what polynomial C means. The NTT is simply a vastly faster route to that exact same C.

Representation checkpoint: where may we actually read score tap Dj+D−1?

Only after the inverse transform has fully returned the product to coefficient form! The score engine can compute the product in transform form, but our target-coefficient proof speaks strictly about coefficient positions.

Check your understanding

What actually makes the target coefficient contain a dot product?

Section summary

  • Schoolbook multiplication demands N² pairs.
  • Fast transforms crush the arithmetic shape down to O(N log N) plus N pointwise products.
  • The NTT changes representation, not the target-coefficient proof.

Repository layer · second pass

What does the NTT accelerate without changing meaning?

Schoolbook negacyclic multiplication considers O(N²) coefficient pairs. The Number Theoretic Transform changes representation so polynomial multiplication becomes pointwise modular multiplication surrounded by forward and inverse transforms, typically O(N log N). It is the finite-field relative of Fourier-transform convolution.

The NTT does not choose score taps, reverse vectors, encrypt data, or remove noise. Those meanings are established elsewhere. Verification should compare inverse-transformed output with an independent coefficient-domain reference.

Reasoning chain

  1. 1

    Begin with the same ring product definition.

  2. 2

    Choose an NTT-friendly modulus and roots.

  3. 3

    Transform both operands.

  4. 4

    Multiply matching transform positions.

  5. 5

    Inverse-transform and normalize.

  6. 6

    Compare every coefficient to the reference.

Worked trace

Separate representation from operation

  1. Coefficient form exposes diagonal buckets.
  2. NTT form exposes N independent point products.
  3. Inverse NTT returns coefficient buckets.
  4. Target taps have the same mathematical values in either route.

Result. Speed changes; the polynomial product contract does not.

Executable lens · Python

Make the hidden state visible

# Contract-level pseudocode
expected = negacyclic(a, b, n)[0]
A, B = ntt(a), ntt(b)
actual = intt([(x*y) % q for x,y in zip(A,B)])
assert actual == expected

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Attributing the dot-product layout to the NTT.
  • Testing transform round-trip but not multiplication.

Retrieval and transfer

Close the book first

  1. Count pairs for N=8 versus N=4096.
  2. List required modulus/root conditions.
  3. Design three independent NTT tests.