All right: Are you a struggling/flourishing/all-together-ok academic on the look-out for that extra paper? Or merely messing around with some polynomials modulo (X^{p}+1) (or (X^{p}-1))?

Here’s your ticket to a free paper:

1. Find a paper that utilizes Bluestein NTT to deal with a tricky non-power-of-two polynomial multiplication (Or improve your own multiplication)
2. See it complain about the fact that picking p is tricky
3. Rewrite to use a Rader NTT instead
4. Profit! (Factor 2 improvement for free!)
5. Extra profit! (You can pick p to be something like (1+ 2^x) , which is good for many schemes) (protip: (65537 = 1+ 2^{16}) is a prime)

Ok fine, I’ll give a bit more explanation

The NTT I’m talking about here is the Number Theoretic Transform. For non-cryptographers: it’s a Fourier Transform that works on numbers modulo some (q) instead of on (\mathbb{C}).

Now the NTT, just like the FFT, is a useful tool for multiplying polynomials together. And multiplying polynomials together is the name of the game for A LOT of public-key cryptography.

Here are three blog posts to get you started on the NTT. But the above is enough information.

Most NTTs (including the blog above) work on polynomials that have a power of two number of coefficients. For example, the Kyber PQC scheme works on polynomials with 256 coefficients (i.e. it works modulo (X^{256}+1)).

But sometimes, a mathematician might for some reason work with polynomials that aren’t powers of two. When they go to write their code, they’ll notice that the standard example of an efficient NTT only works for powers-of-two, and they end up using the Bluestein NTT.

The Bluestein NTT: If something isn’t a power of two, we’ll pad until it is!

Remember that the NTT is a tool for multiplying polynomials together. In the Bluestein NTT, we pretend that our NTT…

(X_j = \sum_{k=0}^{{p-1} x_k \omega}{ jk })

Using the identity jk = -(j–k)2/2 + j2/2 + k2/2

… is a convolution of two carefully constructed series:

(a_k = x_k \omega^{ \frac{k^2}{2} } )

( b_k = \omega^\frac{-k^2 }{2} )

With the convolution looking like:

(X_j =b_k^{-1} \sum_{k=0}^{p-1} a_k b_{n-k} )

We calculate this convolution with NTTs by padding to (M>2p) so that (M) is a power of two. If we then calculate the polynomial multiplication under these NTTs, because (2p) is greater than (M), there will be no overflow over (X^{p}+1).

Just don’t forget to reduce by (X^{p}+1) when you’re done (for the cost of an extra subtraction or two (or three) because of the coefficients of (X^{p}) and onwards).

The Rader NTT: A more elegant approach for a more common situation.

Generally speaking, if the size of our polynomial (p) is already restricted to being a prime, it may be restricted by other specifications. One common restraint for primes is (p \equiv 1 \bmod 2^{x}) with (x) some integer. For a high enough (x), this ensures that Bluestein will require an NTT nearly quadruple the size of the original. Thankfully, Rader’s NTT is a much more elegant solution!*

Rader’s NTT is based on the idea that since (p) is a prime, we can define some (g) that will cycle through the whole group of (\mathbf{Z}_p) except 0.

We then write our NTT down once again:

(X_j = \sum_{k=0}^{{p-1} x_k \omega}{ jk })

And rewrite it as:

(X_0 = \sum_{k=0}^{p-1} x_k )

(X_{g^{-n}} = x_{0}+\sum_{q=0}^{{p-2} x_{g}{q}} \omega^{g^{q}g^{-n} }= x_{0}+\sum_{q=0}^{{p-2} x_{g}{q}} \omega^{g^{-(n-q)} })

This is a convolution of these two series:

(a_q = x_{g^{q}} )

(b_q = \omega^{g^{-q}})

Which can be solved by simply using the NTT again, but this time for a size (p-1) polynomial! If (p) was close to some power of two (i.e. (p \equiv 1 \bmod 2^{x})), then we’re back in the business of doing power of two NTTs, which is easy and efficient.

* Terms and conditions apply: Rader is only applicable if (p) is actually a prime. Do not attempt to use on non-prime (p)’s. Also if that’s the case you should probably stop using notation (p) for a non-prime before the mathematicians start yelling at you.

Conclusion

Bluestein rewrites an NTT as a convolution between two polynomials of size (M>2p) so that (M) is a power of two. This is especially frustrating if (p) is something like (65537 = 2^{16}+1), because it means we have to pick (M=2^{18}>2^{17}+2 = 2p).

Rader rewrites an NTT as a convolution between two polynomials of size (p-1). Obviously, if (p) is something like (65537 = 2^{16}+1), this means a convolution between polynomials of size (2^{16}), which is a straightforward problem to solve using NTTs.

So unless (p) is a Mersenne prime, use Rader! It is mainly not used because it’s not so well known, but it’s far superior as a non-power of two technique over Bluestein, and is usually much better suited to the task. And let me know if you find non-power-of-two applications for polynomials. If you’re not going to take the free papers, I will :).