The Number Theoretic Transform
A Study Club Talk
The (Fast) Fourier Transform
Veritasium made video on this recently.
The Fourier Transform is a way of decomposing a signal into its frequencies
Doing this (fast) is useful in many domains of engineering.
The (Fast) Fourier Transform
Veritasium made video on this recently.
The Fourier Transform is a way of decomposing a signal into its frequencies
Doing this (fast) is useful in many domains of engineering.
The Number Theoretic Transform
Polynomials: Coefficient Form vs Evaluation Form
To produce a STARK, a computer deals with very long polynomials
These polynomials can be expressed in two forms:
The prover has to be able to do operations on both forms
Therefore, we need an efficient way to go back and forth between the two.
From Coefficient Form to Evaluation Form
Starting with p(x) = a3x3 + a2x2 + a1x + a0
How can we get b0 = p(x0), b1 = p(x1), b2 = p(x2), b3 = p(x3) ?
Let’s start with a concrete example, using the finite field 𝔽5.
From Coefficient Form to Evaluation Form
Starting with p(x) = 3x3 + 4x2 + 4x + 1
How can we get b0 = p(1), b1 = p(2), b2 = p(3), b3 = p(4) ?
Let’s start with a concrete example, using the finite field 𝔽5.
Brute-Force is one way... but how much time would it take?
Coefficient to Evaluation as a Matrix
Coefficient to Evaluation as a Matrix
Coefficient to Evaluation as a Matrix
Rewrite as powers of 2!
Coefficient to Evaluation as a Matrix
Rewrite as powers of 2!
Coefficient to Evaluation as a Matrix
Rewrite as powers of 2!
Coefficient to Evaluation as a Matrix
Coefficient to Evaluation as a Matrix
Simplify exponents
Coefficient to Evaluation as a Matrix
Simplify exponents
Coefficient to Evaluation as a Matrix
Switch the rows around
From Coefficient Form to Evaluation Form
Evaluate p(x) = 3x3 + 4x2 + 4x + 1 for x = 2k, for any k.
How can we break the problem down into subproblems?
The Divide-and-Conquer method!
p(x) = 3x3 + 4x2 + 4x + 1
p(x) = 3x3 + 4x + 4x2 + 1
p(x) = x (3x2 + 4) + 4x2 + 1
Call podd(y) = 3y + 4 and peven(y) = 4y + 1
If we can evaluate these polynomials on all powers of (2k)2, we can compute p(x) on any power we want. Let’s see how that works.
From Coefficient Form to Evaluation Form
p(x) = x (3x2 + 4) + 4x2 + 1
We define podd(y) = 3y + 4 and peven(y) = 4y + 1
podd(20) = 3*20 + 4 = 2, podd(22) = 3*22 + 4 = 1
peven(20) = 4*20 + 1 = 0, peven(22) = 4*22 + 1 = 2
p(20) = 20 (3(20)2 + 4) + 4(20)2 + 1 = 20 (3*20 + 4) + 4*20 + 1 = 1 (2) + 0 = 2
p(21) = 21 (3(21)2 + 4) + 4(21)2 + 1 = 21 (3*22 + 4) + 4*22 + 1 = 2 (1) + 2 = 4
p(22) = 22 (3(22)2 + 4) + 4(22)2 + 1 = 22 (3*20 + 4) + 4*20 + 1 = 4 (2) + 0 = 3
p(23) = 23 (3(23)2 + 4) + 4(23)2 + 1 = 23 (3*22 + 4) + 4*22 + 1 = 3 (1) + 2 = 0
From Coefficient Form to Evaluation Form
p(x) = x (3x2 + 4) + 4x2 + 1
This breaks the problem into two subproblems of half the size.
But it’s not too much work to combine the answers of the subproblems into a solution to the big problem.
As such, this can be done much faster than multiplying out the matrix.
(Specifically O(n log n) time)
From Evaluation Form to Coefficient Form
Starting with b0 = p(x0), b1 = p(x1), b2 = p(x2), b3 = p(x3)
How can we get p(x) = a3x3 + a2x2 + a1x + a0 ? (This is like the FFT!)
Let’s remember the matrices again.
From Evaluation Form to Coefficient Form
Starting with b0 = p(x0), b1 = p(x1), b2 = p(x2), b3 = p(x3)
How can we get p(x) = a3x3 + a2x2 + a1x + a0 ? (This is like the FFT!)
Let’s remember the matrices again.
From Evaluation Form to Coefficient Form
Starting with b0 = p(x0), b1 = p(x1), b2 = p(x2), b3 = p(x3)
How can we get p(x) = a3x3 + a2x2 + a1x + a0 ? (This is like the FFT!)
Let’s remember the matrices again.
Now instead of multiplying by the matrix, we must multiply by the inverse.
From Evaluation Form to Coefficient Form
But actually, the inverse of the matrix is very similar to the matrix itself
This means that we can just apply the same algorithm with powers of 3 instead of powers of 2 and we get the coefficient from the evaluations!
Thanks for coming!
Feel free to ask any more questions!
Some Practice Problems
Problem 1
Evaluate the following polynomials using the finite field 𝔽17.
p(x) = 10x7 + 12x6 + 4x5 + 6x4 + 2x3 + 14x2 + 8x + 13
Try doing this using both the brute force method and the NTT method.
Problem 2 (Computer Skills)
The matrix
Was very important to the algorithm we used. In your favorite programming language or Computer Algebra system, write a program that outputs this “NTT” matrix for an arbitrary choice of “2”, and arbitrary field, and an arbitrary number of rows and columns.
Problem 3 (Open-ended)
3a. In the example we showed in the presentation and problem 1, the polynomial has a number of coefficients which is a power of 2. Does the NTT work if this is not the case? What about the reverse NTT?
3b. We mentioned during the presentation that the number “2” is special: we can get every number in 𝔽5 by taking powers of it. What happens if we try to run the NTT with a number that doesn’t have this property?