Number-Theoretic Transform Convolution

Worked Example

To compute the modular convolution of two polynomials, we can evaluate them at roots of unity in a finite field, multiply the evaluations pointwise, and then interpolate the result using the inverse transform. For example, over the field modulo 17 with N=8, we use the primitive root 9.

Consider the "Cyclic wrap" polynomials A = 1 + x^7 and B = 1 + x^2. Pad them to length 8: A = [1, 0, 0, 0, 0, 0, 0, 1] and B = [1, 0, 1, 0, 0, 0, 0, 0].

1. Pad polynomials to length N=8 with zeros if necessary. For A, this gives [1, 0, 0, 0, 0, 0, 0, 1].
2. Apply the forward Number-Theoretic Transform (NTT) to both polynomials using modulus 17 and primitive root 9. The transforms evaluate to aHat = [2, 7, 0, 14, 2, 8, 0, 1] and bHat = [2, 1, 15, 1, 2, 16, 15, 16].
3. Multiply the transformed coefficients pointwise modulo 17, obtaining cHat = [4, 7, 0, 14, 4, 9, 0, 16].
4. Apply the inverse NTT using the inverse primitive root (2) and multiplying by the modular inverse of N (15 modulo 17). This yields the final cyclic convolution coefficients: C = [1, 0, 1, 0, 0, 0, 0, 0], matching the exact expansion modulo (x^8 - 1, 17).

Experiment

Use the interactive module to observe how different polynomial inputs affect the frequency-domain representation and the resulting cyclic convolution coefficients, demonstrating the effect of modulo operations in a finite field.

1. Select a Polynomial type.
2. Observe the resulting transformations.

Launch Number-Theoretic Transform Convolution experiment

Limitations

A Number-Theoretic Transform over a finite field strictly limits the maximum sequence length to divide p-1, and its results are inherently wrapped. It makes no claim to recover unrestricted integer coefficients from a single modulus unless the true maximum convolution value is bounded below the field size.

References

For a deeper dive into polynomial multiplication and transform algorithms, refer to standard resources on competitive programming algorithms.

Fast Fourier transform